oj.uz

Submission #986057

# Submission time Handle Problem Language Result Execution time Memory
986057 2024-05-19T17:03:02 Z yeediot Synchronization (JOI13_synchronization) C++17
100 / 100
 803 ms 35924 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#define why_TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn=1e5+5;
struct BIT{
    int bit[mxn];
    void init(){
        for(int i=0;i<mxn;i++){
            bit[i]=0;
        }
    }
    void modify(int p,int v){
        for(;p<mxn;p+=p&-p){
            bit[p]+=v;
        }
    }
    void modify(int l,int r,int v){
        modify(l,v);
        modify(r+1,-v);
    }
    int query(int p){
        int res=0;
        for(;p;p-=p&-p){
            res+=bit[p];
        }
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l);
    }
}bt;
int n, m, q, timer=0, in[mxn], out[mxn], jump[20][mxn], dep[mxn], ans[mxn], last[mxn];
pair<int,int>edges[mxn];
vector<int>adj[mxn];
bool ex[mxn];
void dfs(int v,int pa){
    in[v]=++timer;
    jump[0][v]=pa;
    dep[v]=dep[pa]+1;
    for(auto u:adj[v]){
        if(u==pa)
            continue;
        dfs(u,v);
    }
    out[v]=timer;
}
int find(int x){
    for(int i=19;i>=0;i--){
        int y=jump[i][x];
        if(bt.query(in[y],in[x])==(1<<i)){
            x=y;
        }
    }
    return x;
}
signed main(){
    why_TOI_is_so_de;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        cin>>edges[i].F>>edges[i].S;
        adj[edges[i].F].pb(edges[i].S);
        adj[edges[i].S].pb(edges[i].F);
    }
    for(int i=1;i<=n;i++){
        ans[i]=1;
    }
    dfs(1,1);
    bt.init();
    for(int i=1;i<n;i++){
        auto &[a,b]=edges[i];
        if(dep[a]<dep[b])swap(a,b);
    }
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            jump[i][j]=jump[i-1][jump[i-1][j]];
        }
    }
    for(int i=0;i<m;i++){
        int id;
        cin>>id;
        auto [v,u]=edges[id];
        int tv=find(v),tu=find(u);
        if(!ex[id]){
            int val=ans[tv]+ans[tu]-last[id];
            last[id]=0;
            bt.modify(in[v],out[v],1);
            ans[tu]=val;
        }
        else{
            last[id]=ans[tu];
            bt.modify(in[v],out[v],-1);
            tv=find(v),tu=find(u);
            ans[tv]=ans[tu]=last[id];
        }
        ex[id]=!ex[id];
    }
    while(q--){
        int x;
        cin>>x;
        cout<<ans[find(x)]<<'\n';
    }
    #ifdef local
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
}
/*
input:
 
*/

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23900 KB Output is correct
2 Correct 3 ms 23900 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 3 ms 23900 KB Output is correct
5 Correct 3 ms 23900 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Correct 26 ms 24412 KB Output is correct
8 Correct 26 ms 24412 KB Output is correct
9 Correct 26 ms 24412 KB Output is correct
10 Correct 803 ms 30832 KB Output is correct
11 Correct 745 ms 30956 KB Output is correct
12 Correct 564 ms 35152 KB Output is correct
13 Correct 375 ms 30500 KB Output is correct
14 Correct 394 ms 30444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 30672 KB Output is correct
2 Correct 144 ms 32460 KB Output is correct
3 Correct 126 ms 34160 KB Output is correct
4 Correct 122 ms 34200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23640 KB Output is correct
2 Correct 4 ms 23900 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 4 ms 23900 KB Output is correct
5 Correct 4 ms 23900 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Correct 28 ms 24996 KB Output is correct
8 Correct 626 ms 35668 KB Output is correct
9 Correct 643 ms 35680 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 33132 KB Output is correct
2 Correct 169 ms 35308 KB Output is correct
3 Correct 171 ms 35512 KB Output is correct
4 Correct 172 ms 35668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23900 KB Output is correct
2 Correct 4 ms 23900 KB Output is correct
3 Correct 3 ms 23900 KB Output is correct
4 Correct 4 ms 23896 KB Output is correct
5 Correct 6 ms 23900 KB Output is correct
6 Correct 31 ms 24596 KB Output is correct
7 Correct 764 ms 31468 KB Output is correct
8 Correct 603 ms 35924 KB Output is correct
9 Correct 404 ms 31680 KB Output is correct
10 Correct 401 ms 31568 KB Output is correct
11 Correct 183 ms 33832 KB Output is correct
12 Correct 178 ms 33740 KB Output is correct
13 Correct 169 ms 35412 KB Output is correct