oj.uz

Submission #97522

# Submission time Handle Problem Language Result Execution time Memory
97522 2019-02-16T17:33:48 Z tincamatei Dreaming (IOI13_dreaming) C++14
18 / 100
 69 ms 13816 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
vector<pair<int, int> > graph[MAX_N];

int dist[MAX_N], papa[MAX_N], distpapa[MAX_N];
int diam[MAX_N], comp[MAX_N], top;
bool viz[MAX_N];

int calcDist(int nod, int p) {
	int rez = nod;
	viz[nod] = true;
	for(auto it: graph[nod]) {
		if(it.first != p) {
			dist[it.first] = dist[nod] + it.second;
			papa[it.first] = nod;
			distpapa[it.first] = it.second;
			int x = calcDist(it.first, nod);
			if(dist[x] >= dist[rez])
				rez = x;
		}
	}
	return rez;
}

int getFarthest(int nod) {
	int x;
	
	dist[nod] = 0;
	papa[nod] = -1;
	nod = calcDist(nod, -1);
	
	x = nod;
	int d = dist[nod];
	top = 0;

	while(nod != -1) {
		diam[top++] = d;
		d -= distpapa[nod];
		nod = papa[nod];
	}

	return x;
}

bool cmp(int a, int b) {
	return a > b;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	int tc = 0;
	for(int i = 0; i < M; ++i) {
		graph[A[i]].push_back(make_pair(B[i], T[i]));
		graph[B[i]].push_back(make_pair(A[i], T[i]));
	}
	
	for(int i = 0; i < N; ++i) {
		if(!viz[i]) {
			int c1, c2;
			c1 = getFarthest(i);
			c2 = getFarthest(c1);
			
			comp[tc] = 2000000000;

			int d = diam[0];
			for(int i = 0; i < top; ++i)
				comp[tc] = min(comp[tc], max(diam[i], d - diam[i]));
			tc++;
		}
	}
	
	sort(comp, comp + tc, cmp);
	if(tc == 1)
		return comp[0];
	else if(tc == 2)
		return comp[0] + comp[1] + L;
	else {
		int rez = 2000000000;
		for(int i = 0; i < 3; ++i) {
			int xd[3], t = 1;
			xd[0] = comp[i];
			for(int j = 0; j < 3; ++j)
				if(i != j)
					xd[t++] = comp[j] + L;
			sort(xd, xd + t, cmp);
			rez = min(rez, xd[0] + xd[1]);
		}
		return rez;
	}
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:12: warning: variable 'c2' set but not used [-Wunused-but-set-variable]
    int c1, c2;
            ^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 13816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 13816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 13816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6588 KB Output is correct
2 Correct 34 ms 6628 KB Output is correct
3 Correct 30 ms 6520 KB Output is correct
4 Correct 30 ms 6400 KB Output is correct
5 Correct 33 ms 6520 KB Output is correct
6 Correct 35 ms 6656 KB Output is correct
7 Correct 42 ms 6648 KB Output is correct
8 Correct 33 ms 6392 KB Output is correct
9 Correct 32 ms 6400 KB Output is correct
10 Correct 39 ms 6648 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 10 ms 4352 KB Output is correct
13 Correct 11 ms 4352 KB Output is correct
14 Correct 10 ms 4352 KB Output is correct
15 Correct 10 ms 4352 KB Output is correct
16 Correct 10 ms 4352 KB Output is correct
17 Correct 10 ms 4224 KB Output is correct
18 Correct 11 ms 4352 KB Output is correct
19 Correct 10 ms 4480 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 4 ms 2816 KB Output is correct
23 Correct 10 ms 4352 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 13816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 13816 KB Output isn't correct
2 Halted 0 ms 0 KB -