oj.uz

Submission #798365

# Submission time Handle Problem Language Result Execution time Memory
798365 2023-07-30T16:03:29 Z QwertyPi Dreaming (IOI13_dreaming) C++14
0 / 100
 28 ms 14604 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 11;
vector<pair<int, int>> G[MAXN];
int D[2][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(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);
	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, q, 0);
    		int rad = INF;
    		for(auto j : vis){
    			rad = min(rad, max(D[0][j], D[1][j]));
			}
			cout << rad << endl;
			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]){
      |           ^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:40:11: warning: unused variable 'p' [-Wunused-variable]
   40 |       int p = max_dis(0, i, 1);
      |           ^
dreaming.cpp:41:22: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |       int q = max_dis(1, q, 0);
      |               ~~~~~~~^~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 14604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 14604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 11348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 14604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -