Submission #1260965

#TimeUsernameProblemLanguageResultExecution timeMemory
1260965raymoo_Railway (BOI17_railway)C++17
0 / 100
157 ms58060 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define eb emplace_back #define umap unordered_map #define prq priority_queue #define vect vector #define rs resize #define bend(v) v.begin(),v.end() #define pob pop_back #define pof pop_front #define lwb lower_bound #define upb upper_bound #define pii pair<int,int> #define nextl cout << '\n' #define el '\n' #define deb cout<<"\nok\n";return #define ll long long #define int long long #define dbl long double #define popcnt __builtin_popcount #define ctz __builtin_ctz #define FILE "ellencute" const ll INF=902337203695775807, N=2e5+69, MOD=1e9+7; void ffopen(){ if(fopen(FILE".inp", "r")){ freopen(FILE".inp", "r", stdin); freopen(FILE".out", "w", stdout); }else if(fopen("ellencute.inp", "r")){ freopen("ellencute.inp", "r", stdin); freopen("ellencute.out", "w", stdout); } } int pm(int a,const int b=1e9+7){return ((a%b)+b)%b;} int sq(int x){return x*x;} ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){ if(a == -1 || b == -1)return -1; ll g = __gcd(a,b); if(b/g > lim/a)return -1; return (a/g)*b; } vect<int> G[N]; int up[N][19], pt[N], t[N], n, mt = 0, add[N], visited[N], D[N], sz[N]; void DFS(int u){ visited[u] = 1; t[++mt] = u; pt[u] = mt; for(int v : G[u]) if(!visited[v]){ D[v] = D[u]+1; up[v][0] = u; DFS(v); sz[u] += sz[v]; } sz[u]++; } void prep(){ up[1][0] = 1; for(int b=1;19>b;b++){ for(int i=1;n>=i;i++){ up[i][b] = up[up[i][b-1]][b-1]; } } } int lca(int u, int v){ if(D[u] < D[v])swap(u, v); int diff= D[u] - D[v], M = -1, tu = u; for(int b=19;b>=0;b--)if((1<<b) <=diff){ u = up[u][b]; diff -= (1<<b); } if(u==v)return u; for(int b=18;b>=0;b--) if(up[u][b] != up[v][b]){ u = up[u][b]; v = up[v][b]; } return up[u][0]; } int bit[N]; void upd(int x, int v){ for(;x<N;x+=x&-x) bit[x] += v; } int get(int x){ int res=0; for(;x>0;x-=x&-x)res += bit[x]; return res; } int cr(int l, int r){ return get(r) - get(l-1); } map<pii, int> mp; void dfs(int u){ visited[u] = 1; for(int v : G[u])if(!visited[v]){ dfs(v); add[u] += add[v]; mp[{u, v}] = mp[{v, u}] = add[v]; } } void sol(){ int q, k; cin >> n >> q >> k; vect<pii> edges; for(int i=1;n>i;i++){ int u, v; cin >> u >> v; G[u].eb(v); G[v].eb(u); edges.eb(u, v); } // deb; DFS(1); prep(); // deb; while(q--){ int m;cin >> m; int b[m]; for(int& i : b){ cin >> i; upd(pt[i], 1); } int L = b[0]; // cout << m << el; for(int i : b){ L = lca(L, i); int child = cr(pt[i], pt[i]+sz[i]-1); child--; if(!child) add[i]++;//, cout << i << el; else add[i] -= child-1; } if(L != 1) add[L]--; for(int& i : b){ upd(pt[i], -1); } } memset(visited, 0, sizeof visited); dfs(1); // deb; for(int i=0;n-1>i;i++){ auto [u, v] = edges[i]; // if(mp[{u, v}] >= k)cout << i << ' ' << mp[{u,v}] << el; // cout << i+1 << ' ' << mp[{u,v}] << el; if(mp[{u,v}] >= 2)cout << i+1 << ' '; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ffopen(); int t=1; //cin >> t; while(t--)sol(); } /* ...-%%%%%%%%%%%... .:**#%=%%%%%+........-%%%%. . .%%%%%%=-..%#. .#%%. %%%+.. .: *%%. .%%. :. :%%%%%:. .%%. ... .: :: .=%%%. ..%%. #%#:%. : :.. =%%. %%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%.. .%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%. .%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%. =%%%...-%%%:::*%********%:::%%%****%::::::::%% .%- .%::::%%***%=:%%**********%%********%:::::::=%-:. .%.. #%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%. .%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%. .%%#%+%%***************##*+=+*==********************%%.:. .%% .%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%. .#%#*********************%%**************++************%%::::::%* .%%%. .%%***************#*****%%%****************************%%::::::%% .-%%%. .#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%. .%%**************#**%%%----%********%%**************#***#%%%#**%#******%* .%%**************#%%%--.....%%*******%%**************#**********#%******%%. .%%*************%%...........%%******%-%*************#***********%%*****%%. .%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%# .%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%% .#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%. .%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%. .+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%- ..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%. .%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%. .%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%. .%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%. ..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%. .%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%. ..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%.. -%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%. .%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%. .%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%. .+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%: =%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%% .%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%% *%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%% .%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%* %%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%. %%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%. .%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%.. :%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% . *%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*.. .%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . ..... %%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%. ..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%# .-%%+. ... .%%%%%%%:. */

Compilation message (stderr)

railway.cpp: In function 'void ffopen()':
railway.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(FILE".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.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(FILE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("ellencute.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen("ellencute.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...
#Verdict Execution timeMemoryGrader output
Fetching results...