oj.uz

Submission #1059083

# Submission time Handle Problem Language Result Execution time Memory
1059083 2024-08-14T16:54:02 Z phong Synchronization (JOI13_synchronization) C++17
100 / 100
 148 ms 22236 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 10 ms 7452 KB Output is correct
8 Correct 9 ms 7516 KB Output is correct
9 Correct 8 ms 7304 KB Output is correct
10 Correct 99 ms 13808 KB Output is correct
11 Correct 103 ms 13756 KB Output is correct
12 Correct 79 ms 21128 KB Output is correct
13 Correct 70 ms 13640 KB Output is correct
14 Correct 69 ms 12636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17156 KB Output is correct
2 Correct 47 ms 16932 KB Output is correct
3 Correct 59 ms 20568 KB Output is correct
4 Correct 43 ms 20816 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 8 ms 4624 KB Output is correct
8 Correct 97 ms 22044 KB Output is correct
9 Correct 84 ms 21844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 22236 KB Output is correct
2 Correct 47 ms 21120 KB Output is correct
3 Correct 48 ms 21972 KB Output is correct
4 Correct 49 ms 21196 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 4804 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 10 ms 3928 KB Output is correct
7 Correct 148 ms 14216 KB Output is correct
8 Correct 91 ms 21684 KB Output is correct
9 Correct 86 ms 14796 KB Output is correct
10 Correct 84 ms 13988 KB Output is correct
11 Correct 53 ms 18256 KB Output is correct
12 Correct 54 ms 18348 KB Output is correct
13 Correct 52 ms 21584 KB Output is correct