oj.uz

답안 #29970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29970 2017-07-21T11:32:37 Z dereotu 꿈 (IOI13_dreaming) C++14
0 / 100
 29 ms 2808 KB 
#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
#define maxx 100005
using namespace std;

priority_queue <pair<int,pair<int,int> > > pq;
int d[3005];
vector<pair<int,int> > adj[3005];
int node,node1,node2;
int groupval[3005],groupnode[3005],m1x,m1;
int vis[3005],id=1;
#define distance sdakadsld
int dis[maxx][2];
int treesize=1;
int ans;
int maxweight=0;

void dfs(int x,int y,int weight,int s,vector<int> &v){
	vis[x]=id;
	v.pb(x);
	forr(i,0,adj[x].size()){
		if(adj[x][i].nd!=y){
			treesize++;
			dfs(adj[x][i].nd,x,weight+adj[x][i].st,s,v);
		}
	}
	if(weight>maxweight){
		maxweight=weight;
		node=x;
	}
	if(s!=2)
		dis[x][s]=weight;
}

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){
		if(A[i]==B[i]) continue;
		adj[A[i]].pb(mp(T[i],B[i]));
		adj[B[i]].pb(mp(T[i],A[i]));
	}
	forr(i,0,N){
		maxweight=-1;
		if(!vis[i]){
			memset(dis,0,sizeof dis);
			vector<int> v;
			dfs(i,-1,0,2,v);
			node1=node;
			maxweight=-1;
			dfs(node1,-1,0,0,v);
			node2=node;
			treesize=1;
			v.clear();
			dfs(node2,-1,0,1,v);
			int starweight=1e9,starnode;
			forr(j,0,v.size()){
				if(starweight>max(dis[v[j]][0],dis[v[j]][1])){
					starweight=max(dis[v[j]][0],dis[v[j]][1]);
					starnode=j;
				}
			}
			groupnode[id]=starnode;
			groupval[id++]=starweight;
		}
	}
	sort(groupval+1,groupval+id+1);
	ans=max(groupval[id-2]+groupval[id-1]+2*L,groupval[id-1]+groupval[id]+L);
	return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int, int, int, std::vector<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:30:7:
  forr(i,0,adj[x].size()){
       ~~~~~~~~~~~~~~~~~           
dreaming.cpp:30:2: note: in expansion of macro 'forr'
  forr(i,0,adj[x].size()){
  ^~~~
dreaming.cpp: In function 'int travelTime(int, int, int, 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:65:9:
    forr(j,0,v.size()){
         ~~~~~~~~~~~~              
dreaming.cpp:65:4: note: in expansion of macro 'forr'
    forr(j,0,v.size()){
    ^~~~
dreaming.cpp:71:17: warning: 'starnode' may be used uninitialized in this function [-Wmaybe-uninitialized]
    groupnode[id]=starnode;
    ~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 1416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -