Submission #279902

#	Time	Username	Problem	Language	Result	Execution time	Memory
279902		amoo_safar	Dreaming (IOI13_dreaming)	C++17	100 / 100	119 ms	17400 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int N = 1e5 + 10;

int mk[N], fr[N], to[N], w[N];
vector<int> G[N], vis;

int dp[N], dp2[N];

void DFS(int u){
	mk[u] = 1;
	vis.pb(u);
	int adj;
	for(auto e : G[u]){
		adj = to[e] ^ fr[e] ^ u;
		if(!mk[adj]){
			DFS(adj);
			dp[u] = max(dp[u], dp[adj] + w[e]);
		}
	}
}
void DFS2(int u, int p){
	int adj, res = dp2[u];
	for(auto e : G[u]){
		adj = to[e] ^ fr[e] ^ u;
		if(adj == p) continue;
		dp2[adj] = max(res + w[e], dp2[adj]);
		res = max(res, dp[adj] + w[e]);
	}
	reverse(G[u].begin(), G[u].end());
	res = dp2[u];
	for(auto e : G[u]){
		adj = to[e] ^ fr[e] ^ u;
		if(adj == p) continue;
		dp2[adj] = max(res + w[e], dp2[adj]);
		res = max(res, dp[adj] + w[e]);
		DFS2(adj, u);
	}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < m; i++){
    	fr[i] = A[i];
    	to[i] = B[i];
    	G[A[i]].pb(i);
    	G[B[i]].pb(i);
    	w[i] = T[i];
    }
    vector<int> V;
    int ans = 0;
    for(int i = 0; i < n; i++){
    	if(mk[i]) continue;
    	vis.clear();
    	DFS(i);
    	DFS2(i, -1);
    	int res = 2000000000;
    	for(auto x : vis) res = min(res, max(dp[x], dp2[x]));
    	for(auto x : vis) ans = max(ans, max(dp[x], dp2[x]));
    	V.pb(res);
    }
    sort(V.begin(), V.end());
    reverse(V.begin(), V.end());
    ans = max(ans, V[0]);
    if(V.size() >= 2) ans = max(ans, L + V[0] + V[1]);
    if(V.size() >= 3) ans = max(ans, L + L + V[1] + V[2]);
    return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23