oj.uz

Submission #445302

# Submission time Handle Problem Language Result Execution time Memory
445302 2021-07-17T11:14:19 Z cpp219 Synchronization (JOI13_synchronization) C++14
30 / 100
 338 ms 28096 KB 
#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 "tst"
    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);
    }

    for (ll i = 1;i <= n;i++) upd(i,1);
    DFS(1,0);
    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[2]); return 0;
    while(Q--){
        cin>>x; //cout<<Jump(x); return 0;
        cout<<info[Jump(x)]<<"\n";
    }

}

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 20972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2676 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2676 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2944 KB Output is correct
7 Correct 23 ms 5188 KB Output is correct
8 Correct 333 ms 28096 KB Output is correct
9 Correct 338 ms 27972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 25104 KB Output is correct
2 Correct 197 ms 27392 KB Output is correct
3 Correct 198 ms 27512 KB Output is correct
4 Correct 201 ms 27536 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -