oj.uz

Submission #445310

# Submission time Handle Problem Language Result Execution time Memory
445310 2021-07-17T11:48:50 Z cpp219 Synchronization (JOI13_synchronization) C++14
100 / 100
 337 ms 28100 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 "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

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.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 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 14 ms 4352 KB Output is correct
8 Correct 13 ms 4364 KB Output is correct
9 Correct 14 ms 4300 KB Output is correct
10 Correct 200 ms 19484 KB Output is correct
11 Correct 201 ms 19524 KB Output is correct
12 Correct 262 ms 27216 KB Output is correct
13 Correct 84 ms 19568 KB Output is correct
14 Correct 136 ms 18492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 20892 KB Output is correct
2 Correct 98 ms 22688 KB Output is correct
3 Correct 124 ms 26376 KB Output is correct
4 Correct 123 ms 26336 KB Output is correct

Subtask #3
10.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 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 22 ms 4948 KB Output is correct
8 Correct 329 ms 25136 KB Output is correct
9 Correct 324 ms 25168 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 25064 KB Output is correct
2 Correct 197 ms 25144 KB Output is correct
3 Correct 199 ms 25112 KB Output is correct
4 Correct 205 ms 25156 KB Output is correct

Subtask #5
40.0 / 40.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 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 18 ms 4412 KB Output is correct
7 Correct 276 ms 20468 KB Output is correct
8 Correct 337 ms 28100 KB Output is correct
9 Correct 105 ms 20576 KB Output is correct
10 Correct 172 ms 19908 KB Output is correct
11 Correct 138 ms 24132 KB Output is correct
12 Correct 139 ms 24120 KB Output is correct
13 Correct 197 ms 27460 KB Output is correct