Submission #171403

#TimeUsernameProblemLanguageResultExecution timeMemory
171403SwanShymbulak (IZhO14_shymbulak)C++14
50 / 100
1097 ms70420 KiB
#include <bits/stdc++.h> #define stop system("pause") #define stop2 char o; cin >> o #define INP freopen("pcb.in","r",stdin) #define OUTP freopen ("pcb.out","w",stdout) //#define int long long using namespace std; const int maxn = 10001; vector<vector<int> > v; bitset<maxn> in_cycle; int color[maxn]; int par[maxn]; int dpth[maxn]; int lift[maxn][16]; int num[maxn]; int kek[maxn][maxn]; int pos_in_cycle[maxn]; vector<int> cycle; int mx; int ans; void get_cycle(int u,int p = -1){ color[u] = 1; par[u] = p; for(int i(0); i < v[u].size();i++){ int to = v[u][i]; if(color[to] == 2)continue; if(color[to] == 1 && to != par[u]){ int now = u; in_cycle[to] = 1; while(now!=to){ pos_in_cycle[now] = cycle.size(); cycle.push_back(now); in_cycle[now] = 1; now = par[now]; } pos_in_cycle[now] = cycle.size(); cycle.push_back(now); }else if(!color[to]){ get_cycle(to,u); } } color[u] = 2; } void build_tree(int u,int p = -1){ if(p!=-1){ lift[u][0] = p; dpth[u] = dpth[p]+1; num[u] = num[p]; }else { lift[u][0] = u; } for(int i(1); i < 16;i++){ lift[u][i] = lift[lift[u][i-1]][i-1]; } for(int i(0); i < v[u].size();i++){ int to = v[u][i]; if(to == p || in_cycle[to])continue; build_tree(to,u); } } int get_lca(int x,int y){ if(dpth[x] > dpth[y])swap(x,y); int delta = abs(dpth[x]-dpth[y]); for(int i(0); i < 17;i++){ int bit = delta&(1<<i); if(!bit)continue; y = lift[y][i]; } if(x == y)return x; for(int i(15);i>=0;i--){ if(lift[x][i]!=lift[y][i]){ x = lift[x][i]; y = lift[y][i]; } } return lift[x][0]; } int get_dist(int x,int y){ int dist = 0; if(num[x] == num[y]){ int lca = get_lca(x,y); kek[x][y] = lca; dist = dpth[x]+dpth[y]-2*dpth[lca]; }else{ dist = dpth[x]+dpth[y]; int fst = pos_in_cycle[num[x]]; int snd = pos_in_cycle[num[y]]; if(fst > snd)swap(fst,snd); int a = abs(snd-fst); int b = cycle.size()-snd+fst; dist+=min(a,b); } return dist; } void solve(int x,int y){ int dist = 0; if(num[x] == num[y]){ int lca = kek[x][y]; dist = dpth[x]+dpth[y]-2*dpth[lca]; if(dist == mx)ans++; }else{ dist = dpth[x]+dpth[y]; int fst = pos_in_cycle[num[x]]; int snd = pos_in_cycle[num[y]]; if(fst > snd)swap(fst,snd); int a = snd-fst; int b = cycle.size()-snd+fst; if(dist+a == mx && a == min(a,b)){ ans++; //cout << "a " << x+1 << ' ' << y+1 << endl; } if(dist+b == mx && b == min(a,b)){ ans++; //cout << "b " << x+1 << ' ' << y+1 << ' ' <<b << ' ' << dist << endl; } } } main(){ ios_base::sync_with_stdio(0); int n; cin >> n; v.resize(n+2); for(int i(0); i < n;i++){ int a,b; cin >> a >> b; a--;b--; v[a].push_back(b); v[b].push_back(a); } get_cycle(0,0); for(int i(0); i < n;i++){ if(in_cycle[i]){ num[i] = i; build_tree(i); } } for(int i(0); i < n;i++){ for(int j(i+1); j < n;j++){ mx = max(mx,get_dist(i,j)); } } for(int i(0); i< n;i++){ for(int j(i+1); j < n;j++){ solve(i,j); } } cout << ans; return 0; } /* */

Compilation message (stderr)

shymbulak.cpp: In function 'void get_cycle(int, int)':
shymbulak.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void build_tree(int, int)':
shymbulak.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:126:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...