Submission #1258120

#TimeUsernameProblemLanguageResultExecution timeMemory
1258120hoangmc2009Synchronization (JOI13_synchronization)C++17
40 / 100
632 ms24172 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; int n,m,q,depth[100009],par[20][100009]; int timer=0,tin[100009],tout[100009]; int sz[100009],pre[100009],st[100009]; i64 BIT[500009]; pair<int,int> e[100009]; vector<int> adj[100009]; void DFS(int u,int pu,int d) { tin[u]=++timer; depth[u]=d; for(int& v:adj[u]) if(v!=pu) DFS(v,u,d+1); tout[u]=timer; par[0][u]=pu; } void update(int i,int v) { while(i<=n) { BIT[i]+=v; i+=(i&-i); } } i64 get(int i) { i64 r=0; while(i>0) { r+=BIT[i]; i-=(i&-i); } return r; } int find_set(int u) { for(int i=19;i>=0;--i) if(get(tin[par[i][u]])==get(tin[u])) u=par[i][u]; return u; } int main() { if(fopen("D:/CPP/THEMIS/test.inp","r")) { freopen("D:/CPP/THEMIS/test.inp","r",stdin); freopen("D:/CPP/THEMIS/test.out","w",stdout); } ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>q; for(int i=1;i<n;++i) { cin>>e[i].first>>e[i].second; adj[e[i].first].push_back(e[i].second); adj[e[i].second].push_back(e[i].first); } DFS(1,0,0); par[0][1]=1; fill(sz,sz+n+1,1); for(int i=1;i<20;++i) for(int j=1;j<=n;++j) par[i][j]=par[i-1][par[i-1][j]]; for(int i=1;i<=n;++i) { if(depth[e[i].first]>depth[e[i].second]) swap(e[i].first,e[i].second); update(tin[i],1); update(tout[i],-1); } for(int x,i=1;i<=m;++i) { cin>>x; if(!st[x]) { sz[find_set(e[x].first)]+=sz[e[x].second]-pre[x]; update(tin[e[x].second],-1); update(tout[e[x].second],1); } else { sz[e[x].second]=pre[x]=sz[find_set(e[x].first)]; update(tin[e[x].second],1); update(tout[e[x].second],-1); } st[x]^=1; } for(int x,i=1;i<=q;++i) { cin>>x; cout<<sz[find_set(x)]<<'\n'; } } /* ........................ ..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::.. ..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+. ..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:. ..:-+*%@@@@@@@%%%##########################################%@@@@+:. ..:=+%@@@@@@%%#####################################################@@@@+.. ....-+%@@@@@@%#############################################################@@@@=.. ..=#@@@@@%%###################################################################%@@@%-. .:+#%@@@@%%#########################################################################%@@@#:. .:=*%@@@%%###############################################################################%@@@@-. ..-*%@@@%%#####################################################################################%@@@=. ..+@@@@###########################################################################################%@@@*.. .*@@@#*##############################################################################################@@@%. .+@@@#**################################################################################################@@@%:. .-%@@#**####%##############################################################################################%@@%:. .+@@#***###%%################################################################################################%@@@-. :#@%****###%%*#################################################################################################%@@@-. -@@%****###@%*###################################################################################################%@@@-. -@@#***###%@#*#####################################################################################################%@@@=. -@@#***###@@#*#######################################################################################################@@@%-. :@@#***###@%**#########################################################################################################@@@+. :%@#***##%@%**##########################################################################################################%@@@. .#@%***##%@%**############################################################################################################%@@*. .+@%***##@@#**##############################################################################################@@##############@@@:. :@@***##@@#**###############################################################################################@@@%############%@@#. .%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=. .*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%. -@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=. .#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%. =@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=. .@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%. .#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@- ..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#. .-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:. ...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*. ..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@. .#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+. :#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%. .+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-. .+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#. .:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:. .....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*. .=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@. .%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=. .+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%. .@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=. .+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%. :@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+. .*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:. :@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#. .*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*. .=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=. -@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=. .+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=. .-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+. ..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#. ...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-. .-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*.. -@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=. .:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+. .+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:. .:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+. .+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+. .#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=. .-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-. ..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:. .=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=.. .=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-. .=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+.. .-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:. ..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+.. .:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:. ..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-. .:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=.. .-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=.. ...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-.. ...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:.. ..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=.. ..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:.. ..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-. ..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-.. .....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:... ..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:.. ...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:.. ...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:.. ...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:.. .*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:.. .@@%****##########@#====%%###@##@%%%@@@%-:.... -@@#****##########@#===+@#***@%=@%###@@%. =@@*****##########%@===#@#***%@=%@###%@@- .*@@*****###########@*==*%%%%%@@+@%###%@@+. .@@%****############%@+=====++==%@#####@@%. =@@#****#############@@========#@######@@@. .*@@*****############@@%@+=====*@#######@@@=. .%@@*****###########%@##@@#===#@########%@@*. -@@%****###########%@%##@%%%*#@##########@@%. =@@#****###########@%###@##%@@###########@@@-. +@@*****##########@@###%@##%@@###########@@@+. .%@@****##########@@####@%##%@@###########%@@%. -@@%****#########@@#####@###%@@############@@@: =@@#****########%@#####%@####@@############@@@=. #@@*****#######%@######@%####@@############%@@#. .%@@****#######%@######%@#####@@############%@@%. -@@%****######%@#######%@#####@@%############@@@-. =@@#****#####%@########@%#####@@%############@@@+. +@@#****####%@########%@######@@%############%@@#. .%@@****####%@#########@@######@@%############%@@@: :@@%****###%@##########@%######@@%#############@@@=. =@@%****##%%##########%@#######@@%#############@@@*. #@@#****#%%###########@@#######@@@#############%@@%. .%@@*****%############%@%#######@@@#############%@@@: -@@@****##############@@########%@@##############@@@+. -@@%****##############@%########%@@##############@@@#. .*@@#****#############@@#########%@@##############%@@@: .%@@*****#############@%#########%@@##############%@@@-. :@@@*****############%@##########%@@###############@@@*. -@@%*****############@%##########%@@###############@@@%. #@@#****############%@############@@###############%@@@: .%@@#****############@%############@@%###############@@@=. :@@@*****###########%@#############@@%###############@@@*. -@@%*****###########@%#############@@%###############@@@%. =@@%*****##########%@##############@@%###############%@@@: .#@@#*****##########@%##############@@%################@@@+. :@@@*****###########@###############@@%################@@@#. */

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("D:/CPP/THEMIS/test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen("D:/CPP/THEMIS/test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...