oj.uz

Submission #96983

# Submission time Handle Problem Language Result Execution time Memory
96983 2019-02-13T06:52:57 Z E869120 Dreaming (IOI13_dreaming) C++14
18 / 100
 100 ms 20724 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, EA, EB, col[1<<18], cnts, dist[1<<18], dist2[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){
	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){
	// 1. get dist(1, a)
	int cols = pos; pos = J[pos][0];
	
	for(int i=0;i<J[pos].size();i++) dist[J[pos][i]]=(1<<30);
	getdist(pos);
	
	int maxp=-1;
	for(int i:J[cols]){
		if(maxp<dist[i]) {maxp = dist[i]; pos = i;}
	}
	
	// 2. get dist(a, b)
	queue<int>que;
	for(int i=0;i<(int)J[cols].size();i++) dist2[J[cols][i]]=(1<<30);
	que.push(pos); dist2[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(dist2[to]>dist2[p]+X[p][i].second){
				dist2[to]=dist2[p]+X[p][i].second;
				que.push(to);
			}
		}
	}
	
	int ans=-1; EA=pos;
	for(int i:J[cols]) {
		if(ans<dist2[i]){ans=dist2[i];EB=i;}
	}
	
	// 3. get dist(b, a)
	for(int i:J[cols]) dist[i]=(1<<30);
	getdist(EB);
	
	int ans2=ans;
	for(int i:J[cols]){
		if(dist[i]+dist2[i]==dist2[EB]) ans2 = min(ans2, max(dist[i], dist2[i]));
	}
	return make_pair(ans, ans2);
}

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=1;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:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<J[pos].size();i++) dist[J[pos][i]]=(1<<30);
              ~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20340 KB Output is correct
2 Correct 86 ms 20724 KB Output is correct
3 Correct 50 ms 17396 KB Output is correct
4 Correct 21 ms 13824 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 28 ms 14504 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 86 ms 20340 KB Output is correct
2 Correct 86 ms 20724 KB Output is correct
3 Correct 50 ms 17396 KB Output is correct
4 Correct 21 ms 13824 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 28 ms 14504 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 86 ms 20340 KB Output is correct
2 Correct 86 ms 20724 KB Output is correct
3 Correct 50 ms 17396 KB Output is correct
4 Correct 21 ms 13824 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 28 ms 14504 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 94 ms 18472 KB Output is correct
2 Correct 90 ms 18468 KB Output is correct
3 Correct 99 ms 18428 KB Output is correct
4 Correct 100 ms 18424 KB Output is correct
5 Correct 88 ms 18552 KB Output is correct
6 Correct 92 ms 18932 KB Output is correct
7 Correct 95 ms 18812 KB Output is correct
8 Correct 97 ms 18292 KB Output is correct
9 Correct 87 ms 18424 KB Output is correct
10 Correct 89 ms 18680 KB Output is correct
11 Correct 12 ms 12672 KB Output is correct
12 Correct 63 ms 17656 KB Output is correct
13 Correct 64 ms 17664 KB Output is correct
14 Correct 61 ms 17528 KB Output is correct
15 Correct 62 ms 17528 KB Output is correct
16 Correct 62 ms 17656 KB Output is correct
17 Correct 65 ms 17528 KB Output is correct
18 Correct 73 ms 17656 KB Output is correct
19 Correct 62 ms 17640 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 12800 KB Output is correct
23 Correct 63 ms 17656 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20340 KB Output is correct
2 Correct 86 ms 20724 KB Output is correct
3 Correct 50 ms 17396 KB Output is correct
4 Correct 21 ms 13824 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 28 ms 14504 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 86 ms 20340 KB Output is correct
2 Correct 86 ms 20724 KB Output is correct
3 Correct 50 ms 17396 KB Output is correct
4 Correct 21 ms 13824 KB Output is correct
5 Correct 19 ms 13440 KB Output is correct
6 Correct 28 ms 14504 KB Output is correct
7 Incorrect 12 ms 12672 KB Output isn't correct
8 Halted 0 ms 0 KB -