제출 #59548

#제출 시각아이디문제언어결과실행 시간메모리
59548TAMREFIslands (IOI08_islands)C++11
80 / 100
1597 ms132096 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,int> pli; const int mx = 1e6 + 5; struct Edg{ int u, v, w; inline int oppo(int x){ return u + v - x; } } E[mx]; vector<int> G[mx]; vector<bool> vis(mx); vector<bool> vis2(mx); vector<bool> dE(mx); int num_cyc = 1; //greater than 1 int n; vector<int> cv; //cycle vertex vector<int> ce; //cycle edge weight vector<ll> Vei, Wei; int OP; int dfs(int x){ int cyc = 0, tcyc, u; vis[x] = 1; for(int &e : G[x]){ if(dE[e]) continue; OP = E[e].oppo(x); if(vis[OP]){ //printf("cycle detected - (%d->%d)\n",x,u); cyc = OP; dE[e] = 1; ce.push_back(E[e].w); }else{ dE[e] = 1; tcyc = dfs(OP); cyc |= tcyc; if(tcyc){ ce.push_back(E[e].w); } } } if(cyc){ //printf("push %d in cv\n",x); cv.push_back(x); } if(cyc == x){ //printf("stopping cycle in %d\n",x); cyc = 0; } return cyc; } ll lans; ll dfs_st(int x){ //dfs for each subtrees in cycle vis2[x] = 1; ll ans = 0, ans2 = 0; for(int &e : G[x]){ OP = E[e].oppo(x); if(!vis2[OP]){ ans2 = max(ans2, dfs_st(OP) + E[e].w); if(ans2 > ans) swap(ans, ans2); } } lans = max(lans, ans + ans2); //local answer in subtree return ans; } inline void BackInsert(deque<pli>& d, pli p){ while(!d.empty() && d.back() <= p) d.pop_back(); d.push_back(p); } inline void OldPop(deque<pli>& d, int k){ while(!d.empty() && d.front().second < k) d.pop_front(); } ll calc(vector<ll>& Vw, vector<int>& E, vector<ll>& sE){ deque<pli> dq; int m = E.size(); ll lsum = E[0]; ll ret = 0; for(int i = 1; i < m; i++){ BackInsert(dq, pli(Vw[i] + sE[i], i)); lsum += E[i]; } for(int i = 0; i < m; i++){ OldPop(dq, i+1); ret = max(ret, Vw[i] - sE[i] + dq.front().first); BackInsert(dq, pli(Vw[i] + lsum + sE[i], i+m)); } dq.clear(); dq.shrink_to_fit(); return ret; } ll dp_on_cycle(){ int C = cv.size(); ll lsum = 0; ll ans = 0; //give cycle-vertices their own number rotate(ce.begin(),ce.begin()+1,ce.end()); //f**k for(int i = 0; i < C; i++){ vis2[cv[i]] = 1; //printf("vertex : %d, clockwise - edge : %d\n",cv[i],ce[i]); } //clockwise for(int i = 0; i < C; i++){ Vei.push_back( dfs_st(cv[i]) ); Wei.push_back( lsum ); lsum += ce[i]; } ans = max(ans, calc(Vei, ce, Wei)); //inclockwise - reversing all the vectors lsum = 0; reverse(cv.begin(),cv.end()); reverse(Vei.begin(),Vei.end()); reverse(ce.begin(), ce.end() - 1); for(int i = 0; i < C; i++){ //printf("vertex : %d, Inc ew : %d\n",cv[i],ce[i]); Wei[i] = lsum; lsum += ce[i]; } ans = max(ans, calc(Vei, ce, Wei)); ans = max(ans, lans); //printf("dp result : %lld\n",ans); return ans; } void input(){ cin >> n; cv.reserve(n); ce.reserve(n); Vei.reserve(n); Wei.reserve(n); for(int i = 1; i <= n; i++){ cin >> E[i].v >> E[i].w; E[i].u = i; G[i].push_back(i); G[E[i].v].push_back(i); } } void debug(const char* S){ /* for(int i = 1; i <= n; i++){ if(G[i].size() > 1){ //printf("deg[%d] = %d\n",i,G[i].size()); for(int &e : G[i]){ if(E[e].w > 90000000) //printf("(%d, %d)\n",E[e].oppo(i),E[e].w); } } } */ FILE *fp = fopen(S,"rt"); ll correct; fscanf(fp,"%lld",&correct); printf("answer = %lld\n",correct); } int main(){ //freopen("isl10.in","rt",stdin); ios_base::sync_with_stdio(false);cin.tie(0); ll ans = 0; input(); for(int i = 1; i <= n; i++){ if(!vis[i]){ cv.clear(); ce.clear(); Wei.clear(); Vei.clear(); dfs(i); lans = 0; ans += dp_on_cycle(); } } cout << ans << '\n'; //debug("isl10.out"); }

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'int dfs(int)':
islands.cpp:31:24: warning: unused variable 'u' [-Wunused-variable]
     int cyc = 0, tcyc, u;
                        ^
islands.cpp: In function 'void debug(const char*)':
islands.cpp:170:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fp,"%lld",&correct);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...