oj.uz

Submission #67519

# Submission time Handle Problem Language Result Execution time Memory
67519 2018-08-14T15:08:59 Z reality Synchronization (JOI13_synchronization) C++17
100 / 100
 1407 ms 96360 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int LG = 20;
const int N = 1e6;
int e[LG][N];
vi g[N];
int s[N];
int bg[N];
int ed[N];
int ans[N];
int lst[N];
int Time = 0;
void dfs(int node = 1,int prev = 1) {
    bg[node] = ++Time;
    e[0][node] = prev;
    for (auto it : g[node])
        if (it != prev)
            dfs(it,node);
    ed[node] = Time + 1;
}
int t[N];
int n;
void upd(int i,int h) {
    for (;i <= n;i += i&(-i))
        t[i] += h;
}
int que(int i) {
    int ans = 0;
    for (;i;i -= i&(-i))
        ans += t[i];
    return ans;
}
int get(int v) {
    const int G = que(bg[v]);
    for (int k = 19;k >= 0;--k)
        if (que(bg[e[k][v]]) == G)
            v = e[k][v];
    return v;
}
vii E;
int main(void) {
    int m,q;
    cin>>n>>m>>q;
    for (int i = 1;i < n;++i) {
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        E.pb(mp(u,v));
    }
    dfs();
    for (int k = 1;k < LG;++k)
        for (int i = 1;i <= n;++i)
            e[k][i] = e[k - 1][e[k - 1][i]];
    for (int i = 0;i + 1 < n;++i)
        if (bg[E[i].fi] > bg[E[i].se])
            swap(E[i].fi,E[i].se);
    for (int i = 1;i <= n;++i)
        upd(bg[i],1),upd(ed[i],-1),ans[i] = 1;
    while (m --) {
        int tp;
        cin>>tp;
        --tp;
        int u = E[tp].fi;
        int v = E[tp].se;
        int g = get(u);
        if (lst[tp] == -1) {
            upd(bg[v],1);
            upd(ed[v],-1);
            lst[tp] = ans[v] = ans[g];
        } else {
            upd(bg[v],-1);
            upd(ed[v],1);
            ans[g] += ans[v] - lst[tp];
            lst[tp] = -1;
        }
    }
    while (q --) {
        int node;
        cin>>node;
        cout << ans[get(node)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 23 ms 24168 KB Output is correct
3 Correct 24 ms 24308 KB Output is correct
4 Correct 23 ms 24308 KB Output is correct
5 Correct 27 ms 24308 KB Output is correct
6 Correct 31 ms 24456 KB Output is correct
7 Correct 83 ms 25880 KB Output is correct
8 Correct 71 ms 26088 KB Output is correct
9 Correct 69 ms 26408 KB Output is correct
10 Correct 1138 ms 41332 KB Output is correct
11 Correct 931 ms 43476 KB Output is correct
12 Correct 1062 ms 50440 KB Output is correct
13 Correct 313 ms 50440 KB Output is correct
14 Correct 624 ms 50440 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 53792 KB Output is correct
2 Correct 287 ms 55688 KB Output is correct
3 Correct 255 ms 59780 KB Output is correct
4 Correct 265 ms 61412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 61412 KB Output is correct
2 Correct 23 ms 61412 KB Output is correct
3 Correct 26 ms 61412 KB Output is correct
4 Correct 27 ms 61412 KB Output is correct
5 Correct 24 ms 61412 KB Output is correct
6 Correct 27 ms 61412 KB Output is correct
7 Correct 76 ms 61412 KB Output is correct
8 Correct 1198 ms 64888 KB Output is correct
9 Correct 1328 ms 67856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 70752 KB Output is correct
2 Correct 491 ms 73156 KB Output is correct
3 Correct 541 ms 75612 KB Output is correct
4 Correct 521 ms 77980 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 77980 KB Output is correct
2 Correct 23 ms 77980 KB Output is correct
3 Correct 25 ms 77980 KB Output is correct
4 Correct 26 ms 77980 KB Output is correct
5 Correct 30 ms 77980 KB Output is correct
6 Correct 102 ms 77980 KB Output is correct
7 Correct 1407 ms 77980 KB Output is correct
8 Correct 1235 ms 83696 KB Output is correct
9 Correct 525 ms 83696 KB Output is correct
10 Correct 842 ms 84384 KB Output is correct
11 Correct 515 ms 89308 KB Output is correct
12 Correct 517 ms 91892 KB Output is correct
13 Correct 477 ms 96360 KB Output is correct