Submission #29603

#	Time	Username	Problem	Language	Result	Execution time	Memory
29603		aybala	Dreaming (IOI13_dreaming)	C++11	0 / 100	1074 ms	14580 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define fori(a,b,c) for(int a=b; a<c; a++)
#define ford(a,b,c) for(int a=b; a>=c; a++)
#define pb push_back
#define pq priority_queue
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
vector< pii >v[100004];
vector< int >el[2];

int vis[100004];
int sp[100004];
int lp[2];
int dis[100004];
int deep[100004];
int g[100004];
int dp[2];
int reans[2];

int dfs(int u, int pre, int gr){
	int s=v[u].size();
	vis[u]=1;
	el[gr].pb(u);
	int res;
	fori(i,0,s){
		if(pre!=v[u][i].fi){
			res=dfs(v[u][i].fi,u,gr);
			dis[u]+=dis[v[u][i].fi]+v[u][i].se;
			
		}
	}
	deep[u]=deep[pre]+1;
	g[u]=gr;
	res=max(res,dis[u]);
	dp[gr]=max(dp[gr],deep[u]-1);
	return res;
}

/*void dfs2(int u, int pre,int gr){
	int s=v[u].size();
	int loc[100004];
	
	fori(i,0,dp[gr]){
		if()
	}
	
	fori(i,0,s){
		if(pre!=v[u][i].fi){
			dfs2(v[u][i],u);
		}
	}
}*/
int n;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n=N;
	fori(i,0,M){
		v[A[i]].pb(mp(B[i],T[i]));
		v[B[i]].pb(mp(A[i],T[i]));
	}
	
	int gr=0;
	fori(i,0,n){
		if(v[i].size()==1 && !vis[i]){
			int k = dfs(i,i,gr);
			int els=el[gr].size();
			int ans=dis[el[gr][els-1]];
			reans[gr]=i;
			fori(j,1,els){
				int loc[100004];
				int locmax=0;
				fori(l,0,els){
					if(l==j){
						loc[l]=0;
					}
					if(l>j){
						loc[l]=dis[el[gr][l]]-dis[el[gr][j]];
					}
					if(l<j){
						loc[l]=dis[el[gr][j]]-dis[el[gr][l]];
					}
					locmax=max(locmax,loc[l]);
				}
				ans=min(locmax,ans);
				reans[gr]=el[gr][j];
				lp[gr]=ans;
			}
			gr++;
		}
	}
	
	return lp[0]+lp[1]+L;	

	
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:8: warning: unused variable 'k' [-Wunused-variable]
    int k = dfs(i,i,gr);
        ^
dreaming.cpp: In function 'int dfs(int, int, int)':
dreaming.cpp:28:6: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int res;
      ^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23