Submission #807707

#	Time	Username	Problem	Language	Result	Execution time	Memory
807707		OAleksa	꿈 (IOI13_dreaming)	C++14	14 / 100	46 ms	13700 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
 
#define f first
#define s second
using namespace std; 
const int maxn = 1e5 + 69;
vector<pair<int, int>> g[maxn];
vector<int> vis(maxn), d(maxn), d1(maxn);
vector<int> t, s;
int c, mn = 1e9;
void dfs(int v, int p) {
	vis[v] = 1;
	t.push_back(v);
	d[v] = 0;
	int mx1 = 0, mx2 = 0;
	for(auto u : g[v]) {
		if(u.f != p) {
			dfs(u.f, v);
			if(d[u.f] + u.s > mx1) {
				mx2 = mx1;
				mx1 = d[u.f] + u.s;
			}
			else if(d[u.f] + u.s > mx2)
				mx2 = d[u.f] + u.s;
		}
	}
	d[v] = mx1;
	d1[v] = mx1 + mx2;
}

void dfs1(int v, int p, int x, int t) {
	if(v == x) {
		int mx1 = 0, mx2 = 0;
		int l1 = -1, l2 = -1;
		for(auto u : g[v]) {
			if(u.f != p) {
				if(d[u.f] + u.s > mx1) {
					mx2 = mx1;
					l2 = l1;
					l1 = u.f;
					mx1 = d[u.f] + u.s;
				}
				else if(d[u.f] + u.s > mx2) {
					mx2 = d[u.f] + u.s;
					l2 = u.f;
				}
			}
		}
		int x = max(mx1, mx2);
		if(x < mn) {
			c = v;
			mn = x;
		}
		dfs1(l1, v, x, t);
		if(l2 != -1)
			dfs1(l2, v, x, t);
	}
	else {
		int k = -1, mx = 0;
		for(auto u : g[v]) {
			if(u.f != p) {
				if(d[u.f] + u.s >= mx) {
					k = u.f;
					mx = d[u.f] + u.s;
				}
			}
		}
		
		int x = max(mx, t - mx);
		if(k != -1) {
			if(x < mn) {
				c = v;
				mn = x;
			}
			dfs1(k, v, x, t);
		}
	}
}


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]});
  }
  for(int i = 0;i < N;i++) {
  	if(!vis[i]) {
  		t.clear();
  		dfs(i, -1);
  		mn = 1e9;
  		c = -1;
  		int mx = 0, l = 0;
  		for(auto u : t) {
  			if(d1[u] >= mx) {
  				mx = d1[u];
  				l = u;
  			}
  		}
  		dfs1(l, -1, l, mx);
  		s.push_back(c);
  	}
  }
  for(int i = 1;i < (int)s.size();i++) {
  	g[s[i]].push_back({s[i - 1], L});
  	g[s[i - 1]].push_back({s[i], L});
  }
  dfs(0, -1);
  int ans = 0;
  for(int i = 0;i < N;i++) 
  	ans = max(ans, d1[i]);
  return ans;
}

//  
// int main()
// {
	  // ios_base::sync_with_stdio(false);
	  // cin.tie(0);
	  // cout.tie(0);
	  // int tt = 1;
		// //cin >> tt;
	  // while(tt--) {
			// int n, m, l;
			// cin >> n >> m >> l;
			// int a[m], b[m], t[m];
			// for(int i = 0;i < m;i++) 
				// cin >> a[i] >> b[i] >> t[i];
			// cout << travelTime(n, m, l, a, b, t);
		// }
    // return 0;
// }

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