Submission #29729

#	Time	Username	Problem	Language	Result	Execution time	Memory
29729		dereotu	Dreaming (IOI13_dreaming)	C++14	0 / 100	30 ms	2808 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define forr(i,A,B) for(int i=A;i<B;++i)
#define space ' '
#define endl '\n'
#define LL long long
using namespace std;

priority_queue <pair<int,pair<int,int> > > pq;
int d[3005];
vector<pair<int,int> > adj[3005];
int dp[3005][3005];
int groupval[3005],groupnode[3005],m1x,m1;
int vis[3005];
#define distance sdakadsld

int findset(int x){
	if(d[x]==x) return x;
	return d[x]=findset(d[x]);
}

void unionset(int x,int y){
	d[findset(x)]=d[findset(y)];
}

void dfs(int x,int y,int root){
	forr(i,0,adj[x].size()){
		if(adj[x][i].nd!=y){
			dp[root][adj[x][i].nd]=dp[root][x]+adj[x][i].st;
			dfs(adj[x][i].nd,x,root);
		}
	}
}

int distance(int x,int weight){
    vis[x] = true;
    bool check = false;
    forr(i,0,adj[x].size()){
        if(!vis[adj[x][i].nd]){
            check = true;
            distance(adj[x][i].nd,weight+adj[x][i].st);
        }
    }
    if(!check and weight>m1){
        m1 = weight;
        m1x = x;
    }
    vis[x] = false;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	forr(i,0,N) d[i]=i;
	forr(i,0,N){
		adj[A[i]].pb(mp(T[i],B[i]));
		adj[B[i]].pb(mp(T[i],A[i]));
		if(findset(A[i])!=findset(B[i])){
			unionset(A[i],B[i]);
		}
	}
	forr(i,0,N){
		dfs(i,-1,i);
	}
	memset(groupval,1,sizeof groupval);
	memset(groupnode,-1,sizeof groupnode);
	int node1=-1,node2=-1,best=1e9,secondbest=1e9,ans=0;
	forr(i,0,N){
		int maxval=0;
		forr(j,0,N){
			maxval=max(maxval,dp[i][j]);
		}
		if(maxval<best){
			secondbest=best;
			node2=node1;
			node1=i;
			best=maxval;
		}
		else if(maxval<secondbest){
			secondbest=maxval;
			node2=i;
		}
	}
	adj[node1].pb(mp(L,node2));
	adj[node2].pb(mp(L,node1));
	memset(dp,0,sizeof dp);
	forr(i,0,N){
		forr(j,0,N){
			ans=max(ans,dp[i][j]);
		}
	}
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
dreaming.cpp:32:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
dreaming.cpp:32:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
dreaming.cpp: In function 'int sdakadsld(int, int)':
dreaming.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
dreaming.cpp:43:10:
     forr(i,0,adj[x].size()){
          ~~~~~~~~~~~~~~~~~        
dreaming.cpp:43:5: note: in expansion of macro 'forr'
     forr(i,0,adj[x].size()){
     ^~~~
dreaming.cpp:54:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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