Submission #445310

#	Time	Username	Problem	Language	Result	Execution time	Memory
445310		cpp219	Synchronization (JOI13_synchronization)	C++14	100 / 100	337 ms	28100 KiB

synchronization

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
LL edge[N];
vector<ll> g[N];
ll n,m,Q,x,y,id,nTime = 1,cur[N],par[N][Log2];
ll L[N],R[N],d[N],bit[N],info[N],last[N];

void DFS(ll u,ll p){
    for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
        par[u][i] = par[par[u][i - 1]][i - 1];
    L[u] = R[u] = nTime; nTime++;
    for (auto i : g[u]) if (i != p){
        par[i][0] = u;
        d[i] = d[u] + 1; DFS(i,u); R[u] = max(R[u],R[i]);
    }
}

void upd(ll p,ll val){
    for (ll i = p;i <= n;i += i & -i) bit[i] += val;
}

ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}

ll Jump(ll node){
    ll lca = node;
    for (ll i = Log2 - 1;i >= 0;i--){
        ll nxt = par[lca][i];
        if (nxt && Get(L[nxt]) == Get(L[node])) lca = nxt;
    }
    return lca;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }

    cin>>n>>m>>Q; fill(info,info + n + 1,1);
    for (ll i = 1;i < n;i++){
        cin>>x>>y; edge[i] = {x,y};
        g[x].push_back(y); g[y].push_back(x);
    }
        DFS(1,0);
    for (ll i = 1;i <= n;i++){

        upd(L[i],1); upd(R[i] + 1,-1);
    }

    while(m--){
        cin>>id;
        x = edge[id].fs; y = edge[id].sc;
        if (par[x][0] == y) swap(x,y);

        ll nxt = Jump(x);
        if (!cur[id]){
            info[nxt] += info[y] - last[y];
            upd(L[y],-1); upd(R[y] + 1,1);
        }
        else{
            info[y] = last[y] = info[nxt];
            upd(L[y],1); upd(R[y] + 1,-1);
        }
        cur[id] ^= 1; //cout<<Get(L[3]); return 0;
    }
    //cout<<info[1]; return 0;
    while(Q--){
        cin>>x; //cout<<Jump(x); return 0;
        cout<<info[Jump(x)]<<"\n";
    }

}

Compilation message (stderr)

synchronization.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
synchronization.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
synchronization.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
synchronization.cpp: In function 'int main()':
synchronization.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40