제출 #302357

#제출 시각아이디문제언어결과실행 시간메모리
302357HemimorIslands (IOI08_islands)C++14
100 / 100
1360 ms108508 KiB
#include <algorithm> #include <iostream> #include <iomanip> #include <numeric> #include <cassert> #include <vector> #include <cmath> #include <queue> #include <set> #include <map> #define syosu(x) fixed<<setprecision(x) using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> P; typedef pair<double,double> pdd; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<string> vs; typedef vector<P> vp; typedef vector<vp> vvp; typedef vector<pll> vpll; typedef pair<int,P> pip; typedef vector<pip> vip; const int inf=1<<30; const ll INF=1ll<<60; const double pi=acos(-1); const double eps=1e-8; const ll mod=1e9+7; const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; const int M=1000000; int n,deg[M]; bool vis[M]; vp g[M]; ll res,c[M],d[M]; void f(int v){ res=0; vi a,b; vis[v]=1; queue<int> q; q.push(v); while(!q.empty()){ v=q.front();q.pop(); a.push_back(v); for(auto p:g[v]){ int u=p.first; if(!vis[u]){ vis[u]=1; q.push(u); } } } for(auto i:a) if(deg[i]==1) q.push(i); while(!q.empty()){ v=q.front();q.pop(); deg[v]--; ll X=0,Y=0; for(auto p:g[v]){ int u=p.first; if(deg[u]){ deg[u]--; if(deg[u]==1) q.push(u); } else{ ll t=d[u]+abs(p.second); d[v]=max(d[v],t); if(t>X){ Y=X; X=t; } else if(t>Y) Y=t; } } res=max(res,X+Y); } for(auto i:a) if(deg[i]){ v=i; ll X=0,Y=0; for(auto p:g[v]){ int u=p.first; if(!deg[u]){ ll t=d[u]+abs(p.second); d[v]=max(d[v],t); if(t>X){ Y=X; X=t; } else if(t>Y) Y=t; } } res=max(res,X+Y); } int now=v; ll t=0; do{ b.push_back(now); c[now]=t; for(auto p:g[now]){ int u=p.first; if(p.second>0){ now=u; t+=p.second; } } }while(now!=v); ll mx=-INF; for(auto i:b){ res=max(res,c[i]+d[i]+mx); mx=max(mx,-c[i]+d[i]); } mx=-INF; for(auto i:b){ res=max(res,t-c[i]+d[i]+mx); mx=max(mx,c[i]+d[i]); } } int main(){ scanf("%d",&n); for(int u=0;u<n;u++){ int v,w; scanf("%d%d",&v,&w); v--; g[u].push_back({v,w}); g[v].push_back({u,-w}); deg[u]++,deg[v]++; } ll sum=0; for(int i=0;i<n;i++) if(!vis[i]){ f(i); sum+=res; } printf("%lld\n",sum); }

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

islands.cpp: In function 'int main()':
islands.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
islands.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%d%d",&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~
#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...