oj.uz

Submission #987134

# Submission time Handle Problem Language Result Execution time Memory
987134 2024-05-22T04:29:49 Z guagua0407 Synchronization (JOI13_synchronization) C++17
100 / 100
 464 ms 30984 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e5+5;
vector<int> adj[mxn];
vector<int> dp[mxn];
int up[mxn][20];
int st[mxn],en[mxn];
bool ok[mxn];
int depth[mxn];
int bit[mxn];
int cnt[mxn];
int timer=0;

void update(int pos,int val){
    for(;pos<mxn;pos+=(pos&-pos)){
        bit[pos]+=val;
    }
}

int query(int pos){
    int ans=0;
    for(;pos>0;pos-=(pos&-pos)){
        ans+=bit[pos];
    }
    return ans;
}

void dfs(int v,int p=0){
    up[v][0]=p;
    st[v]=++timer;
    depth[v]=depth[p]+1;
    dp[v].push_back(v);
    cnt[v]=1;
    for(auto u:adj[v]){
        if(u==p) continue;
        dfs(u,v);
    }
    en[v]=timer;
}

int go(int v,int len){
    for(int i=0;i<20;i++){
        if(len&(1<<i)) v=up[v][i];
    }
    return v;
}

int get(int b){
    int ans=0;
    for(int i=19;i>=0;i--){
        int tmp=ans+(1<<i);
        int v=go(b,tmp);
        int val=query(st[b])-query(st[v]);
        if(val>=tmp){
            ans=tmp;
        }
    }
    return go(b,ans);
}

int main() {_
    int n,m,q;
    cin>>n>>m>>q;
    vector<pair<int,int>> e(n-1);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        e[i]={a,b};
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> qs;
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        x--;
        qs.push_back(x);
    }
    int root=1;
    dfs(root);
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            up[i][j]=up[up[i][j-1]][j-1];
        }
    }
    for(auto x:qs){
        int a=e[x].f;
        int b=e[x].s;
        if(depth[a]>depth[b]) swap(a,b);
        if(ok[x]){
            int v=get(a);
            cnt[b]=cnt[v];
            ok[x]=false;
            update(st[b],-1);
            update(en[b]+1,1);
            continue;
        }
        ok[x]=true;
        update(st[b],1);
        update(en[b]+1,-1);
        int v=get(b);
        assert(v!=0);
        cnt[v]+=(int)dp[b].size();
        if(dp[v].size()<dp[b].size()) swap(dp[v],dp[b]);
        dp[v].insert(dp[v].end(),all(dp[b]));
        dp[b].clear();
    }
    for(int i=1;i<=n;i++){
        cnt[i]=cnt[get(i)];
    }
    for(int i=0;i<q;i++){
        int x;
        cin>>x;
        cout<<cnt[x]<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message

synchronization.cpp: In function 'void setIO(std::string)':
synchronization.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 6 ms 5360 KB Output is correct
7 Correct 26 ms 7260 KB Output is correct
8 Correct 25 ms 7260 KB Output is correct
9 Correct 26 ms 7260 KB Output is correct
10 Correct 375 ms 26308 KB Output is correct
11 Correct 303 ms 25800 KB Output is correct
12 Correct 341 ms 30164 KB Output is correct
13 Correct 228 ms 26008 KB Output is correct
14 Correct 258 ms 25804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 28188 KB Output is correct
2 Correct 204 ms 27872 KB Output is correct
3 Correct 222 ms 29484 KB Output is correct
4 Correct 213 ms 29384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 5 ms 5212 KB Output is correct
7 Correct 28 ms 7512 KB Output is correct
8 Correct 348 ms 30952 KB Output is correct
9 Correct 464 ms 30948 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 30984 KB Output is correct
2 Correct 230 ms 30280 KB Output is correct
3 Correct 225 ms 30568 KB Output is correct
4 Correct 222 ms 30536 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5208 KB Output is correct
2 Correct 3 ms 5208 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 5 ms 5212 KB Output is correct
6 Correct 26 ms 7256 KB Output is correct
7 Correct 327 ms 26688 KB Output is correct
8 Correct 432 ms 30968 KB Output is correct
9 Correct 230 ms 27124 KB Output is correct
10 Correct 294 ms 26776 KB Output is correct
11 Correct 228 ms 29500 KB Output is correct
12 Correct 266 ms 29384 KB Output is correct
13 Correct 237 ms 30360 KB Output is correct