oj.uz

Submission #96984

# Submission time Handle Problem Language Result Execution time Memory
96984 2019-02-13T06:59:58 Z E869120 Dreaming (IOI13_dreaming) C++14
18 / 100
 171 ms 20216 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int> >X[1<<18]; vector<int> J[1<<18], G;
int N, M, L, col[1<<18], cnts, dist[1<<18];

void dfs(int pos){
	if(col[pos]>=1) return;
	col[pos]=cnts; J[cnts].push_back(pos);
	for(int i=0;i<X[pos].size();i++) dfs(X[pos][i].first);
}

void getdist(int pos){
	for(int i:J[col[pos]]) dist[i]=(1<<30);
	queue<int>que; que.push(pos); dist[pos]=0;
	
	while(!que.empty()){
		int p = que.front(); que.pop();
		for(int i=0;i<(int)X[p].size();i++) {
			int to = X[p][i].first;
			if(dist[to]>dist[p]+X[p][i].second){
				dist[to]=dist[p]+X[p][i].second;
				que.push(to);
			}
		}
	}
}

pair<int, int> radius(int pos){
	getdist(J[pos][0]);
	int EA=0,ret1=-1; for(int i:J[pos]) {if(ret1<dist[i]){ret1=dist[i];EA=i;}}
	getdist(EA); vector<int> A1;
	int EB=0,ret2=-1; for(int i:J[pos]) {if(ret2<dist[i]){ret2=dist[i];EB=i;A1.push_back(dist[i]);}}
	getdist(EB); vector<int> A2;
	for(int i:J[pos]) A2.push_back(dist[i]);
	
	int ret=dist[EA];
	for(int i=0;i<A1.size();i++){if(dist[EA]==A1[i]+A2[i]) ret=min(ret,max(A1[i],A2[i]));}
	return make_pair(dist[EA], ret);
}

int travelTime(int NN, int MM, int LL, int A[], int B[], int T[]) {
    N = NN; M = MM; L = LL;
    for(int i=0;i<M;i++){
		X[A[i]].push_back(make_pair(B[i], T[i]));
		X[B[i]].push_back(make_pair(A[i], T[i]));
	}
	for(int i=0;i<N;i++){
		if(col[i]>=1) continue;
		cnts++;dfs(i);
	}
	
	int maxn=0;
	for(int i=1;i<=cnts;i++){
		pair<int, int>I1 = radius(i); maxn = max(maxn, I1.first);
		//cout<<i<<":"<<I1.first<<" "<<I1.second<<endl;
		G.push_back(I1.second);
	}
	sort(G.begin(), G.end());
	reverse(G.begin(), G.end());
	
	if(G.size()==1) return maxn;
	
	int rem=(1<<30);
	for(int i=0;i<(int)G.size();i++){
		int v1 = G[i]; vector<int>v2;
		for(int j=0;j<(int)G.size();j++){
			if(j != i) v2.push_back(G[j]);
			if(v2.size()==2) break;
		}
		int s1 = v1 + v2[0] + L;
		int s2 = 0; if(v2.size()==2) s2 = v2[0] + v2[1] + L * 2;
		rem = min(rem, max(s1, s2));
	}
	return max(maxn, rem);
}

Compilation message

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:11:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X[pos].size();i++) dfs(X[pos][i].first);
              ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> radius(int)':
dreaming.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A1.size();i++){if(dist[EA]==A1[i]+A2[i]) ret=min(ret,max(A1[i],A2[i]));}
              ~^~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20216 KB Output is correct
2 Correct 84 ms 20212 KB Output is correct
3 Correct 51 ms 18164 KB Output is correct
4 Correct 20 ms 13760 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 27 ms 14464 KB Output is correct
7 Incorrect 12 ms 12672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20216 KB Output is correct
2 Correct 84 ms 20212 KB Output is correct
3 Correct 51 ms 18164 KB Output is correct
4 Correct 20 ms 13760 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 27 ms 14464 KB Output is correct
7 Incorrect 12 ms 12672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20216 KB Output is correct
2 Correct 84 ms 20212 KB Output is correct
3 Correct 51 ms 18164 KB Output is correct
4 Correct 20 ms 13760 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 27 ms 14464 KB Output is correct
7 Incorrect 12 ms 12672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 18052 KB Output is correct
2 Correct 105 ms 18012 KB Output is correct
3 Correct 103 ms 18144 KB Output is correct
4 Correct 110 ms 18144 KB Output is correct
5 Correct 114 ms 18052 KB Output is correct
6 Correct 171 ms 18580 KB Output is correct
7 Correct 107 ms 18376 KB Output is correct
8 Correct 100 ms 17908 KB Output is correct
9 Correct 103 ms 17912 KB Output is correct
10 Correct 107 ms 18296 KB Output is correct
11 Correct 12 ms 12672 KB Output is correct
12 Correct 86 ms 17268 KB Output is correct
13 Correct 87 ms 17284 KB Output is correct
14 Correct 85 ms 17272 KB Output is correct
15 Correct 84 ms 17272 KB Output is correct
16 Correct 85 ms 17272 KB Output is correct
17 Correct 85 ms 17144 KB Output is correct
18 Correct 89 ms 17272 KB Output is correct
19 Correct 86 ms 17272 KB Output is correct
20 Correct 12 ms 12672 KB Output is correct
21 Correct 12 ms 12672 KB Output is correct
22 Correct 14 ms 12772 KB Output is correct
23 Correct 87 ms 17272 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20216 KB Output is correct
2 Correct 84 ms 20212 KB Output is correct
3 Correct 51 ms 18164 KB Output is correct
4 Correct 20 ms 13760 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 27 ms 14464 KB Output is correct
7 Incorrect 12 ms 12672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20216 KB Output is correct
2 Correct 84 ms 20212 KB Output is correct
3 Correct 51 ms 18164 KB Output is correct
4 Correct 20 ms 13760 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 27 ms 14464 KB Output is correct
7 Incorrect 12 ms 12672 KB Output isn't correct
8 Halted 0 ms 0 KB -