oj.uz

Submission #957685

# Submission time Handle Problem Language Result Execution time Memory
957685 2024-04-04T07:56:43 Z guagua0407 Synchronization (JOI13_synchronization) C++17
30 / 100
 230 ms 28620 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 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);
    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 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;
    cin>>root;
    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]){
            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 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;
            }
        }
        int v=go(b,ans);
        assert(v!=0);
        if(dp[v].size()<dp[b].size()) swap(dp[v],dp[b]);
        dp[v].insert(dp[v].end(),all(dp[b]));
        dp[b].clear();
    }
    cout<<(int)dp[root].size()<<'\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 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 16 ms 11356 KB Output is correct
8 Correct 16 ms 11356 KB Output is correct
9 Correct 16 ms 11356 KB Output is correct
10 Correct 203 ms 25472 KB Output is correct
11 Correct 230 ms 25704 KB Output is correct
12 Correct 190 ms 27592 KB Output is correct
13 Correct 143 ms 25148 KB Output is correct
14 Correct 174 ms 25500 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 25800 KB Output is correct
2 Correct 147 ms 26572 KB Output is correct
3 Correct 135 ms 28620 KB Output is correct
4 Correct 138 ms 28216 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 27332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8284 KB Output isn't correct
2 Halted 0 ms 0 KB -