oj.uz

Submission #672537

# Submission time Handle Problem Language Result Execution time Memory
672537 2022-12-16T14:22:45 Z Hacv16 Dreaming (IOI13_dreaming) C++17
0 / 100
 69 ms 61392 KB 
#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;

#define fr first
#define sc second

int r1, r2, mxdiam, d[MAX], dist[MAX], pai[MAX];
int mx, mxx, id;
bool seen[MAX];
vector<pair<int, int>> adj[MAX];

void dfs(int u, int p, int dt, int dtt, bool f){
	if(dt == mx && dtt > mxx) mxx = dtt, id = u;
	if(dt > mx) id = u, mx = dt, mxx = dtt;
	mxdiam = max(mxdiam, dtt);

	if(f) pai[u] = p, d[u] = dt, dist[u] = dtt; 

	seen[u] = true;

	for(auto e : adj[u]){ 
		int v = e.fr, w = e.sc;
		if(v == p) continue;
		dfs(v, u, dt + 1, dtt + w, f);
	}
}

int getRadius(int u){
	mx = -1; mxx = -1;
	dfs(u, -1, 0, 0, 0);

	int ponta1 = id;
	
	mx = -1; mxx = -1;
	dfs(ponta1, -1, 0, 0, 1);

	int ponta2 = id;
    
    if(ponta1 == ponta2) return 0;
    
	int cur = ponta2;
	vector<int> path;

	while(cur != -1){
		path.push_back(cur);
		cur = pai[cur];
	}

	if(path.size() % 2){
		int cent = path[path.size() / 2];
		return max(dist[cent], dist[ponta2] - dist[cent]);

	}else{
		int cent1 = path[path.size() / 2];
		int cent2 = path[path.size() / 2 - 1];

		int mxr1 = max(dist[cent1], dist[ponta2] - dist[cent1]);
		int mxr2 = max(dist[cent2], dist[ponta2] - dist[cent2]);

		if(mxr1 <= mxr2) return mxr1;
		return mxr2;
	}

	return -INF;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]){
	for(int i = 0; i < m; i++){
		int u = A[i], v = B[i], w = T[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	for(int i = 0; i < n; i++){
		if(seen[i]) continue;
		int r = getRadius(i);
		
		if(r > r1){ swap(r1, r2); r1 = r; }
		else if(r > r2) { r2 = r; }
	}
	
	return max(mxdiam, L + r1 + r2);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 61392 KB Output is correct
2 Correct 61 ms 61288 KB Output is correct
3 Correct 47 ms 56548 KB Output is correct
4 Correct 33 ms 49364 KB Output is correct
5 Correct 27 ms 48360 KB Output is correct
6 Correct 35 ms 50372 KB Output is correct
7 Incorrect 25 ms 47284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 61392 KB Output is correct
2 Correct 61 ms 61288 KB Output is correct
3 Correct 47 ms 56548 KB Output is correct
4 Correct 33 ms 49364 KB Output is correct
5 Correct 27 ms 48360 KB Output is correct
6 Correct 35 ms 50372 KB Output is correct
7 Incorrect 25 ms 47284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 51228 KB Output is correct
2 Incorrect 45 ms 51184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 61392 KB Output is correct
2 Correct 61 ms 61288 KB Output is correct
3 Correct 47 ms 56548 KB Output is correct
4 Correct 33 ms 49364 KB Output is correct
5 Correct 27 ms 48360 KB Output is correct
6 Correct 35 ms 50372 KB Output is correct
7 Incorrect 25 ms 47284 KB Output isn't correct
8 Halted 0 ms 0 KB -