/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 2.027 MiB
#2 Accepted 5ms 2.02 MiB
#3 Wrong Answer 5ms 2.023 MiB
#4 Wrong Answer 7ms 2.312 MiB
#5 Wrong Answer 50ms 9.203 MiB
#6 Wrong Answer 90ms 9.82 MiB
#7 Wrong Answer 77ms 9.684 MiB
#8 Wrong Answer 28ms 2.176 MiB
#9 Wrong Answer 67ms 2.961 MiB
#10 Wrong Answer 107ms 9.793 MiB
#11 Wrong Answer 75ms 10.215 MiB
#12 Wrong Answer 91ms 9.574 MiB
#13 Wrong Answer 41ms 10.258 MiB
#14 Wrong Answer 127ms 10.25 MiB
#15 Wrong Answer 44ms 3.496 MiB
#16 Wrong Answer 40ms 9.617 MiB
#17 Wrong Answer 42ms 9.609 MiB
#18 Wrong Answer 43ms 9.609 MiB
#19 Accepted 123ms 52.309 MiB
#20 Wrong Answer 137ms 52.543 MiB
#21 Wrong Answer 136ms 52.492 MiB
#22 Accepted 146ms 60.121 MiB
#23 Wrong Answer 310ms 52.203 MiB
#24 Wrong Answer 290ms 52.199 MiB
#25 Wrong Answer 140ms 52.535 MiB
#26 Accepted 12ms 4.844 MiB

Code

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define ll long long
#define mod 1000000007
#define int long long
#define all(x)      x.begin(),x.end()
#define allr(x)     x.rbegin(),x.rend()
#define CheckBit(x,k)   (x & (1LL << k))
#define SetBit(x,k)     (x |= (1LL << k))
#define ClearBit(x,k)   (x &= ~(1LL << k))
#define LSB(mask)       __builtin_ctzll(mask)
#define MSB(mask)       63-__builtin_clzll(mask) 
#define print(x)    cout << #x << " : " << x << endl
#define error1(x)   cerr << #x << " = " << (x) <<endl
#define coutall(v)  for(auto &it: v) cout<<it<<' '; cout<<endl
#define Abid_52     ios::sync_with_stdio(false);cin.tie(0),cin.tie(0)
#define error2(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n"
#define UNIQUE(x)   sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T, typename U> T ceil(T x, U y) {return (x > 0 ? (x + y - 1) / y : x / y);}
template <typename T, typename U> T floor(T x, U y) {return (x > 0 ? x / y : (x - y + 1) / y);}
const int N = 2e5 + 10;
const int Log = 20;
vector<int> g[N + 1];
int timer = 0;
int tin[N + 1];  // for node entering time
int tout[N + 1]; // for node existing time
int table[N + 1][Log + 1];
int level[N + 1];
int apple[N + 5];
vector<int>vis(N + 5, 0);
int track = -1;
int ans = 0;
int mx = -1;
int secondNode = -1;
void reset(int n)
{
    for (int i = 1; i <= n + 5; i++)
    {
        g[i].clear();
        tin[i] = 0;
        tout[i] = 0;
        level[i] = 0;
        vis[i] = 0;
        for (int j = 0; j < Log; j++)
        {
            table[i][j] = -1;
        }
    }
    timer = 0;
    track = -1;
    ans = 0;
    mx = -1;
    secondNode = -1;
}
void dfs(int node, int par, int lev = 0)
{
    tin[node] = ++timer; // node entering time
    table[node][0] = par;
    level[node] = lev;
    for (int i = 1; i < Log; i++)
    {
        int p = table[node][i - 1];
        table[node][i] = table[p][i - 1];
    }
    for (int child : g[node])
    {
        if (child != par)
        {
            dfs(child, node, lev + 1);
        }
    }
    tout[node] = ++timer; // node existing time
}
bool isAncestor(int u, int v) // check if u is ancestor of v or not
{
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int u, int v)
{
    if (isAncestor(u, v))
    {
        return u;
    }
    if (isAncestor(v, u))
    {
        return v;
    }
    for (int i = Log - 1; i >= 0; i--)
    {
        if (!isAncestor(table[u][i], v))
        {
            u = table[u][i];
        }
    }
    return table[u][0];
}
int distance(int u, int v) // distance between two node u and v
{
    int l = lca(u, v);
    return level[u] + level[v] - (level[l] << 1); // level[u]+level[v]-2*level[lca(u,v)]
}
int kth(int u, int k)
{
    for (int i = 0; i <= Log; i++)
        if (k & (1 << i))
            u = table[u][i];
    return u;
}
int findKth(int u, int v, int k) // kth node from u to v, 0th node is u
{
    int l = lca(u, v);
    int d = level[u] + level[v] - (level[l] << 1);
    if (level[l] + k <= level[u])
        return kth(u, k);
    k -= level[u] - level[l];
    return kth(v, level[v] - level[l]-k);
}
void dfs1(int node){
    // print(node);
    vis[node] = 1;
    if(track == -1)track = node;
    if(track != -1 && apple[node] == 1){
        // print(node);
        // print(track);
        ans += (distance(node, track));
        track = node;
    }
    for(auto it : g[node]){
        if(!vis[it]){
            dfs1(it);
        }
    }
}
void dfs2(int node,int root){
    vis[node] = 1;
    if(apple[node] == 1){
        // print(node);
        int dis = distance(node, root);
        if(dis > mx){
            mx = dis;
            secondNode = node;
        }
    }
    // print(node);
    for(auto it : g[node]){
        if(!vis[it]){
            dfs2(it, root);
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    reset(n);
    int app = -1,cnt = 0;
    for(int i = 1; i <= n; i++){
        cin >> apple[i];
        if(apple[i] == 1){
            app = i;
        }
        if(apple[i] == 1)cnt++;
    }
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(app == -1 || cnt == 1 || cnt == 0){
        cout << 0 << endl;
        return;
    }
    dfs(1, 1);
    dfs2(app, app);
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
    }
    dfs1(app);
    int firstAns = ans;
    ans = 0;
    track = -1;
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
    }
    dfs1(secondNode);
    // print(app);
    // print(secondNode);
    int secondAns = ans;
    cout << min(firstAns, secondAns) << endl;
    // for (int i = 1; i <= n; i++)
    // {
    //     for (int j = 0; j <= 10; j++)
    //     {
    //         cout << table[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // int q;
    // cin >> q;
    // while (q--)
    // {
    //     int a, b;
    //     cin >> a >> b;
    //     cout << lca(a, b) << endl;
    //     // cout << distance(a, b) << endl;
    // }
    // print(distance(1, 8));
    // cout << ans << endl;
}

int32_t main()
{
    Abid_52;
    int t = 1;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc)
    {
        // cout << "Case " << tc << ":";
        solve();
    }
}

Information

Submit By
Type
Submission
Problem
P1078 Apple on Tree
Contest
Bangladesh 2.0
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-16 17:32:45
Judged At
2024-10-03 13:21:37
Judged By
Score
22
Total Time
310ms
Peak Memory
60.121 MiB