제출 #427195

#제출 시각아이디문제언어결과실행 시간메모리
427195AmineWeslati꿈 (IOI13_dreaming)C++14
47 / 100
1075 ms16320 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int>vi; #define pb push_back #define sz(v) (int)v.size() typedef pair<int,int>pi; #define fi first #define se second typedef vector<pi>vpi; #define eb emplace_back #define FOR(i,a,b) for(int i=a; i<b; i++) #define ROF(i,a,b) for(int i=b-1; i>=a; i--) void ckmax(int &x, int y){x=max(x,y);} void ckmin(int &x, int y){x=min(x,y);} const int MX=1e5+10; //----------------------------- int N,M; vpi adj[MX]; vi vis(MX,0); vi dist(MX); pi par[MX]; void dfs(int u){ vis[u]=1; for(auto it: adj[u]){ int v=it.fi,w=it.se; if(dist[v]==-1){ dist[v]=dist[u]+w; par[v]={u,w}; dfs(v); } } } int u2,v2,m2,c,d; void solve(int u){ FOR(i,0,N) dist[i]=-1; dist[u]=0; dfs(u); int v=u; FOR(i,0,N) if(dist[i]!=-1 && dist[i]>dist[v]) v=i; u=v; FOR(i,0,N) dist[i]=-1; dist[u]=0; dfs(u); v=u; FOR(i,0,N) if(dist[i]!=-1 && dist[i]>dist[v]) v=i; int diam=dist[v]; tie(u2,v2)={u,v}; int cur=0,mn=2e9; m2=v; c=0; d=0; while(u!=v){ cur+=par[v].se; v=par[v].fi; if(max(diam-cur,cur)<mn){ mn=max(diam-cur,cur); m2=v; c=diam-cur; d=cur; } } } void find_middle(int u, int v){ FOR(i,0,N) dist[i]=-1; dist[u]=0; dfs(u); int diam=dist[v]; int cur=0,mn=2e9; m2=v; c=0; d=0; while(u!=v){ cur+=par[v].se; v=par[v].fi; if(max(diam-cur,cur)<mn){ mn=max(diam-cur,cur); m2=v; c=diam-cur; d=cur; } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { ::N=N; ::M=M; FOR(i,0,M){ int u=A[i],v=B[i],w=T[i]; adj[u].eb(v,w); adj[v].eb(u,w); } int u=-1,v,m,a,b; FOR(i,0,N) if(!vis[i]){ solve(i); //cout << i << endl; //cout << u2 << ' ' << v2 << ' ' << m2 << ' ' << c << ' ' << d << endl; if(u==-1){ tie(u,v)={u2,v2}; m=m2; tie(a,b)={c,d}; } else{ if(c+d>max(a+b, max(a,b)+max(c,d)+L) ){ tie(u,v)={u2,v2}; m=m2; tie(a,b)={c,d}; } else if(max(a,b)+max(c,d)+L>max(a+b,c+d)){ adj[m].eb(m2,L); adj[m2].eb(m,L); int nu,nv; if(a>=b) nu=u; else nu=v; if(c>=d) nv=u2; else nv=v2; tie(u,v)={nu,nv}; //cout << u << ' ' << v << endl; //cout << m << ' '<< m2 << endl; //cout << endl; find_middle(u,v); m=m2; a=c; b=d; //cout << m << endl; } } } return a+b; } /* 12 8 2 0 8 4 8 2 2 2 7 4 5 11 3 5 1 7 1 3 1 1 9 5 10 6 3 18 */ /* 12 10 5 0 1 2 0 2 3 0 3 1 1 4 4 1 5 1 3 6 6 7 8 5 7 9 5 5 10 5 5 11 5 22 */

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

dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:16:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 | #define FOR(i,a,b) for(int i=a; i<b; i++)
      |                    ^~~
dreaming.cpp:45:5: note: in expansion of macro 'FOR'
   45 |     FOR(i,0,N) dist[i]=-1; dist[u]=0;
      |     ^~~
dreaming.cpp:45:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |     FOR(i,0,N) dist[i]=-1; dist[u]=0;
      |                            ^~~~
dreaming.cpp:16:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 | #define FOR(i,a,b) for(int i=a; i<b; i++)
      |                    ^~~
dreaming.cpp:52:5: note: in expansion of macro 'FOR'
   52 |     FOR(i,0,N) dist[i]=-1; dist[u]=0;
      |     ^~~
dreaming.cpp:52:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   52 |     FOR(i,0,N) dist[i]=-1; dist[u]=0;
      |                            ^~~~
dreaming.cpp: In function 'void find_middle(int, int)':
dreaming.cpp:16:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 | #define FOR(i,a,b) for(int i=a; i<b; i++)
      |                    ^~~
dreaming.cpp:77:5: note: in expansion of macro 'FOR'
   77 |     FOR(i,0,N) dist[i]=-1; dist[u]=0;
      |     ^~~
dreaming.cpp:77:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |     FOR(i,0,N) dist[i]=-1; dist[u]=0;
      |                            ^~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:146:14: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |     return a+b;
      |              ^
dreaming.cpp:146:14: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
#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...