제출 #807054

#제출 시각아이디문제언어결과실행 시간메모리
807054YassirSalama꿈 (IOI13_dreaming)C++17
47 / 100
755 ms17696 KiB
#include "dreaming.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define all(v) v.begin(),v.end() #define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n"; void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__); #define pb push_back #define F first #define S second const ll INF=1e9; const int MAXN=1e5+100; int n,m,l; vector<vector<pair<int,int>>> v(MAXN); vector<pair<ll,ll>> diameters; bool visited[MAXN]; ll parr[MAXN]; ll depth[MAXN]; vector<int> abc; pair<ll,ll> dfs(int node,int par,ll ew=0){//depth, best node visited[node]=true; parr[node]=par; depth[node]=ew; // dbg(node,par,ew); if(v[node].size()==1&&v[node][0].F==par){ return {ew,node}; } ll ans=0; ll best=node; for(auto x:v[node]){ if(x.F!=par){ // dbg(x.F,node,ew,x.S); pair<ll,ll> p=dfs(x.F,node,ew+x.S); if(p.F>ans){ ans=p.F; best=p.S; } } } return {ans,best}; } ll bigdia=0; int par[MAXN]; int f=0; void find_diameter(int node){ pair<ll,ll> p=dfs(node,node); int f=p.S; memset(parr,0,sizeof(parr)); p=dfs(p.S,p.S); // dbg(f,p.S); vector<ll> dia; while(p.S!=parr[p.S]) { dia.push_back(p.S); p.S=parr[p.S]; } dia.push_back(p.S); reverse(all(dia)); bigdia=p.F; abc.push_back(p.F); int nodea=0; int nodeb=0; int a,b,c,e; ll besta=INF; ll bestb=INF; for(auto x:dia){ a=depth[dia.back()]-depth[x]; b=depth[x]; if(besta>max(a,b)){ besta=max(a,b); nodea=x; } par[x]=dia[0]; } // if(besta==INF){ // dbg(node); // } // assert(besta==INF); diameters.pb({besta,nodea}); // dbg(besta,nodea); // OVL(dia," ") f++; } struct Edge{ ll a,b; ll c; bool operator < (const Edge& other) const{ return c<other.c; } }; int find(int node){ if(node==par[node]) return node; return par[node]=find(par[node]); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N; m=M; l=L; memset(visited,false,sizeof(visited)); for(int i=0;i<m;i++){ v[A[i]].push_back({B[i],T[i]}); v[B[i]].push_back({A[i],T[i]}); } memset(depth,0,sizeof(depth)); for(int i=0;i<n;i++){ if(!visited[i]){ find_diameter(i); } } vector<Edge> edges; int d=diameters.size(); // cout<<d<<endl; bool ok=true; for(int i=0;i<n;i++){ ok&=(v[i].size()<=1); } sort(all(abc)); bigdia=abc.back(); sort(all(diameters),greater<pair<int,int>>()); if(diameters.size()==1) return bigdia; if(diameters.size()==2) return max(bigdia,diameters[0].F+diameters[1].F+l); else return max({bigdia ,diameters[diameters.size()-1].F+diameters[diameters.size()-2].F+l, diameters[diameters.size()-2].F+diameters[diameters.size()-3].F+2*L}); for(int i=0;i<d-1;i++){ int nodea=diameters[i].S; ll besta=diameters[i].F; int nodeb=-1; ll bestb=INF; edges.push_back({.a=nodea,.b=diameters[i+1].S,.c=besta+(i+1)*l+diameters[i+1].F}); // dbg(nodea,nodeb); } sort(all(edges)); for(auto& edge:edges){ if(find(edge.a)==find(edge.b)) continue; int a=find(edge.a); int b=find(edge.b); par[b]=a; // dbg(edge.a,edge.b,edge.c); // dbg(a,b,edge.a,edge.b); v[edge.a].pb({edge.b,l}); v[edge.b].pb({edge.a,l}); } memset(depth,0LL,sizeof(depth)); find_diameter(0); //working for sub4 //here we have every element have at most one return bigdia; } #ifdef IOI #define fail(s, x...) do { \ fprintf(stderr, s "\n", ## x); \ exit(1); \ } while(0) #define MAX_N 100000 static int A[MAX_N]; static int B[MAX_N]; static int T[MAX_N]; int main() { int N, M, L, i; int res; FILE *f = fopen("dreaming.in", "r"); if (!f) fail("Failed to open input file."); res = fscanf(f, "%d%d%d", &N, &M, &L); for (i = 0; i < M; i++) res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]); fclose(f); int answer = travelTime(N, M, L, A, B, T); printf("%d\n", answer); return 0; } #endif

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

dreaming.cpp: In function 'void find_diameter(int)':
dreaming.cpp:63:9: warning: unused variable 'nodeb' [-Wunused-variable]
   63 |     int nodeb=0;
      |         ^~~~~
dreaming.cpp:64:13: warning: unused variable 'c' [-Wunused-variable]
   64 |     int a,b,c,e;
      |             ^
dreaming.cpp:64:15: warning: unused variable 'e' [-Wunused-variable]
   64 |     int a,b,c,e;
      |               ^
dreaming.cpp:66:8: warning: unused variable 'bestb' [-Wunused-variable]
   66 |     ll bestb=INF;
      |        ^~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:129:13: warning: unused variable 'nodeb' [-Wunused-variable]
  129 |         int nodeb=-1;
      |             ^~~~~
dreaming.cpp:130:12: warning: unused variable 'bestb' [-Wunused-variable]
  130 |         ll bestb=INF;
      |            ^~~~~
#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...