Submission #1059083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059083		phong	Synchronization (JOI13_synchronization)	C++17	100 / 100	148 ms	22236 KiB

synchronization

#include<bits/stdc++.h>

#define ll long long
const int nmax =  1e5+ 5, N = 1e6;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m, q;
vector<int> adj[nmax];
int h[nmax], par[nmax], sz[nmax];

void dfs(int u, int p){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        par[v] = u;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
int head[nmax], ind[nmax], pos[nmax], Time = 0, nchain = 1;
int lol[nmax];

void dfs_2(int u, int p){
    if(!head[nchain]) head[nchain] = u;
    ind[u] = nchain;
    pos[u] = ++Time;
    lol[Time] = u;
    int idx = -1;
    for(auto v : adj[u]){
        if(v == p) continue;
        if(idx == -1 || sz[v] > sz[idx]) idx = v;
    }
    if(idx != -1) dfs_2(idx, u);
    for(auto v : adj[u]){
        if(v == p) continue;
        if(idx == v) continue;
        ++nchain;
        dfs_2(v, u);
    }
}
int rev[nmax];
struct SEG_1{
    int tree[nmax << 2];
    void update(int id, int l,int r, int u, int val){
        if(l > u || r < u) return;
        if(l == r){
            tree[id] = val;
            return;
        }
        int mid = r + l >> 1;
        update(id << 1, l, mid, u, val);
        update(id << 1 | 1, mid + 1, r, u, val);
        tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
    }
    int get(int id, int l,int r, int u, int v){
        if(tree[id] == 1) return -1;
        if(l >= u && r <= v){
            while(l != r){
                int mid = r + l >> 1;
                if(!tree[id << 1 | 1]){
                    id = id << 1 | 1;
                    l = mid + 1;
                }
                else {
                    id = id << 1;
                    r = mid;
                }
            }
            return l;
        }
        int mid = r + l >> 1;
        if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
        if(mid + 1 > v) return get(id << 1, l, mid, u, v);
        int t1 = get(id << 1 | 1, mid + 1, r, u, v);
        if(t1 != -1) return t1;
        return get(id << 1, l, mid, u, v);
    }
}one;
pii a[nmax];
int res[nmax],last[nmax];
int Find(int u){
    int uchain = ind[u], achain = ind[1];
    while(1){
        if(uchain == achain){
            int kq = one.get(1, 1, n, pos[1], pos[u]);
            return lol[kq];
        }
        int kq = one.get(1, 1, n, pos[head[uchain]], pos[u]);
        if(kq != -1) return lol[kq];
        u = par[head[uchain]];
        uchain = ind[u];
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        cin >> a[i].fi >> a[i].se;
        adj[a[i].fi].push_back(a[i].se);
        adj[a[i].se].push_back(a[i].fi);
    }
    dfs(1, -1);
    dfs_2(1, -1);
    for(int i = 1; i <= n; ++i){
        int &u = a[i].fi;
        int &v = a[i].se;
        if(h[u] > h[v]) swap(u, v);
        res[i] = 1;
    }

    for(int i = 1,x; i <= m; ++i){
        cin >> x;
        int u = a[x].fi, v= a[x].se;
        if(!rev[x]){
            one.update(1, 1, n, pos[v], 1);
            int root = Find(v);
            res[root] += res[v] - last[v];
        }
        else{
            int root = Find(v);
            one.update(1, 1, n, pos[v], 0);
            res[v] = res[root];
            last[v] = res[root];
        }
        rev[x] ^= 1;

//    for(int i = 1; i <= n; ++i) cout << Find(i) << ' ';
//    cout << endl;

    }
    for(int i = 1, x; i <= q; ++i){
        cin >> x;
        cout << res[Find(x)] << endl;
    }
}
/*



*/

Compilation message (stderr)

synchronization.cpp: In member function 'void SEG_1::update(int, int, int, int, int)':
synchronization.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = r + l >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int SEG_1::get(int, int, int, int, int)':
synchronization.cpp:68:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |                 int mid = r + l >> 1;
      |                           ~~^~~
synchronization.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = r + l >> 1;
      |                   ~~^~~
synchronization.cpp: At global scope:
synchronization.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main(){
      | ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:125:13: warning: unused variable 'u' [-Wunused-variable]
  125 |         int u = a[x].fi, v= a[x].se;
      |             ^

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