oj.uz

Submission #798376

# Submission time Handle Problem Language Result Execution time Memory
798376 2023-07-30T16:17:37 Z QwertyPi Dreaming (IOI13_dreaming) C++14
18 / 100
 34 ms 15188 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 11;
vector<pair<int, int>> G[MAXN];
int D[3][MAXN];
vector<int> vis;
void dfs(int sl, int v, int pa = -1){
	vis.push_back(v);
	for(auto [u, w] : G[v]){
		if(u != pa){
			D[sl][u] = D[sl][v] + w; dfs(sl, u, v);
		}
	}
	return;
}

int max_dis(int sl, int v, bool clear){
	int u = -1;
	D[sl][v] = 0; dfs(sl, v); 
	for(auto i : vis){
		if(u == -1 || D[sl][i] > D[sl][u]){
			u = i;
		}
	}
	if(clear) vis.clear();
	return u;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i = 0; i < M; i++) G[A[i]].push_back({B[i], T[i]}), G[B[i]].push_back({A[i], T[i]});
    const int INF = 1 << 30;
	fill(D[0], D[0] + N, INF);
	fill(D[1], D[1] + N, INF);
	fill(D[2], D[2] + N, INF);
	vector<int> rads;
    for(int i = 0; i < N; i++){
    	if(D[0][i] == INF){
    		int p = max_dis(0, i, 1);
    		int q = max_dis(1, p, 1);
    		max_dis(2, q, 0);
    		int rad = INF;
    		for(auto j : vis){
    			rad = min(rad, max(D[1][j], D[2][j]));
			}
			rads.push_back(rad);
			vis.clear();
		}
	}
	sort(rads.begin(), rads.end(), [](int x, int y){
		return x > y;
	});
	if(rads.size() == 1) return rads[0];
	else if(rads.size() == 2) return rads[0] + rads[1] + L;
	else return max(rads[0] + rads[1] + L, rads[1] + rads[2] + L * 2);
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:12:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   12 |  for(auto [u, w] : G[v]){
      |           ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 15188 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 16 ms 6404 KB Output is correct
2 Correct 16 ms 6900 KB Output is correct
3 Correct 16 ms 6896 KB Output is correct
4 Correct 15 ms 6868 KB Output is correct
5 Correct 15 ms 6868 KB Output is correct
6 Correct 16 ms 7316 KB Output is correct
7 Correct 18 ms 7100 KB Output is correct
8 Correct 15 ms 6828 KB Output is correct
9 Correct 19 ms 6780 KB Output is correct
10 Correct 16 ms 6996 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 5 ms 4432 KB Output is correct
13 Correct 5 ms 4460 KB Output is correct
14 Correct 5 ms 4432 KB Output is correct
15 Correct 5 ms 4432 KB Output is correct
16 Correct 5 ms 4432 KB Output is correct
17 Correct 5 ms 4432 KB Output is correct
18 Correct 5 ms 4456 KB Output is correct
19 Correct 5 ms 4432 KB Output is correct
20 Correct 1 ms 2664 KB Output is correct
21 Correct 1 ms 2664 KB Output is correct
22 Correct 1 ms 2664 KB Output is correct
23 Correct 7 ms 4432 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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