Submission #1257957

#TimeUsernameProblemLanguageResultExecution timeMemory
1257957hoangmc2009Synchronization (JOI13_synchronization)C++17
10 / 100
8092 ms327680 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; int n,m,q,st[100009]; pair<int,int> e[100009]; set<int> adj[100009],res[100009]; void DFS(int u,int pu,vector<int>& x) { for(int& y:x) res[u].insert(y); for(const int& v:adj[u]) if(v!=pu) DFS(v,u,x); } void connect(int i) { adj[e[i].first].insert(e[i].second); adj[e[i].second].insert(e[i].first); vector<int> a,b; for(const int& x:res[e[i].first]) {if(res[e[i].second].find(x)==res[e[i].second].end()) b.push_back(x);} for(const int& x:res[e[i].second]) {if(res[e[i].first].find(x)==res[e[i].first].end()) a.push_back(x);} DFS(e[i].first,0,a); DFS(e[i].second,0,b); } void disconn(int i) { adj[e[i].first].erase(e[i].second); adj[e[i].second].erase(e[i].first); } 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; for(int i=1;i<=n;++i) res[i].insert(i); for(int x,i=1;i<=m;++i) { cin>>x; if(!st[x]) connect(x); else disconn(x); st[x]^=1; } for(int x,i=1;i<=q;++i) { cin>>x; cout<<res[x].size()<<'\n'; } } /* ........................ ..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::.. ..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+. ..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:. ..:-+*%@@@@@@@%%%##########################################%@@@@+:. ..:=+%@@@@@@%%#####################################################@@@@+.. ....-+%@@@@@@%#############################################################@@@@=.. ..=#@@@@@%%###################################################################%@@@%-. .:+#%@@@@%%#########################################################################%@@@#:. .:=*%@@@%%###############################################################################%@@@@-. ..-*%@@@%%#####################################################################################%@@@=. ..+@@@@###########################################################################################%@@@*.. .*@@@#*##############################################################################################@@@%. .+@@@#**################################################################################################@@@%:. .-%@@#**####%##############################################################################################%@@%:. .+@@#***###%%################################################################################################%@@@-. :#@%****###%%*#################################################################################################%@@@-. -@@%****###@%*###################################################################################################%@@@-. -@@#***###%@#*#####################################################################################################%@@@=. -@@#***###@@#*#######################################################################################################@@@%-. :@@#***###@%**#########################################################################################################@@@+. :%@#***##%@%**##########################################################################################################%@@@. .#@%***##%@%**############################################################################################################%@@*. .+@%***##@@#**##############################################################################################@@##############@@@:. :@@***##@@#**###############################################################################################@@@%############%@@#. .%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=. .*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%. -@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=. .#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%. =@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=. .@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%. .#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@- ..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#. .-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:. ...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*. ..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@. .#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+. :#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%. .+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-. .+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#. .:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:. .....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*. .=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@. .%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=. .+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%. .@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=. .+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%. :@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+. .*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:. :@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#. .*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*. .=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=. -@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=. .+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=. .-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+. ..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#. ...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-. .-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*.. -@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=. .:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+. .+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:. .:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+. .+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+. .#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=. .-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-. ..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:. .=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=.. .=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-. .=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+.. .-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:. ..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+.. .:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:. ..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-. .:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=.. .-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=.. ...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-.. ...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:.. ..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=.. ..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:.. ..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-. ..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-.. .....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:... ..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:.. ...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:.. ...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:.. ...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:.. .*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:.. .@@%****##########@#====%%###@##@%%%@@@%-:.... -@@#****##########@#===+@#***@%=@%###@@%. =@@*****##########%@===#@#***%@=%@###%@@- .*@@*****###########@*==*%%%%%@@+@%###%@@+. .@@%****############%@+=====++==%@#####@@%. =@@#****#############@@========#@######@@@. .*@@*****############@@%@+=====*@#######@@@=. .%@@*****###########%@##@@#===#@########%@@*. -@@%****###########%@%##@%%%*#@##########@@%. =@@#****###########@%###@##%@@###########@@@-. +@@*****##########@@###%@##%@@###########@@@+. .%@@****##########@@####@%##%@@###########%@@%. -@@%****#########@@#####@###%@@############@@@: =@@#****########%@#####%@####@@############@@@=. #@@*****#######%@######@%####@@############%@@#. .%@@****#######%@######%@#####@@############%@@%. -@@%****######%@#######%@#####@@%############@@@-. =@@#****#####%@########@%#####@@%############@@@+. +@@#****####%@########%@######@@%############%@@#. .%@@****####%@#########@@######@@%############%@@@: :@@%****###%@##########@%######@@%#############@@@=. =@@%****##%%##########%@#######@@%#############@@@*. #@@#****#%%###########@@#######@@@#############%@@%. .%@@*****%############%@%#######@@@#############%@@@: -@@@****##############@@########%@@##############@@@+. -@@%****##############@%########%@@##############@@@#. .*@@#****#############@@#########%@@##############%@@@: .%@@*****#############@%#########%@@##############%@@@-. :@@@*****############%@##########%@@###############@@@*. -@@%*****############@%##########%@@###############@@@%. #@@#****############%@############@@###############%@@@: .%@@#****############@%############@@%###############@@@=. :@@@*****###########%@#############@@%###############@@@*. -@@%*****###########@%#############@@%###############@@@%. =@@%*****##########%@##############@@%###############%@@@: .#@@#*****##########@%##############@@%################@@@+. :@@@*****###########@###############@@%################@@@#. */

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("D:/CPP/THEMIS/test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         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...