제출 #798400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798400		QwertyPi	Dreaming (IOI13_dreaming)	C++14	100 / 100	76 ms	18008 KiB

dreaming

#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;
	int ans = 0;
    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]));
    			ans = max(ans, 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) ans = max(ans, rads[0]);
	else if(rads.size() == 2) ans = max(ans, rads[0] + rads[1] + L);
	else ans = max(ans, max(rads[0] + rads[1] + L, rads[1] + rads[2] + L * 2));
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23