oj.uz

Submission #807707

# Submission time Handle Problem Language Result Execution time Memory
807707 2023-08-04T22:25:52 Z OAleksa Dreaming (IOI13_dreaming) C++14
14 / 100
 46 ms 13700 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13572 KB Output is correct
2 Correct 34 ms 13068 KB Output is correct
3 Correct 31 ms 11696 KB Output is correct
4 Correct 7 ms 5256 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 10 ms 6044 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 17 ms 7936 KB Output is correct
9 Correct 29 ms 9996 KB Output is correct
10 Correct 2 ms 3924 KB Output is correct
11 Correct 33 ms 11212 KB Output is correct
12 Correct 46 ms 12052 KB Output is correct
13 Correct 3 ms 3856 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3848 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Incorrect 2 ms 3796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13572 KB Output is correct
2 Correct 34 ms 13068 KB Output is correct
3 Correct 31 ms 11696 KB Output is correct
4 Correct 7 ms 5256 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 10 ms 6044 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 17 ms 7936 KB Output is correct
9 Correct 29 ms 9996 KB Output is correct
10 Correct 2 ms 3924 KB Output is correct
11 Correct 33 ms 11212 KB Output is correct
12 Correct 46 ms 12052 KB Output is correct
13 Correct 3 ms 3856 KB Output is correct
14 Correct 2 ms 3848 KB Output is correct
15 Correct 2 ms 3796 KB Output is correct
16 Correct 2 ms 3796 KB Output is correct
17 Correct 2 ms 3796 KB Output is correct
18 Correct 2 ms 3796 KB Output is correct
19 Incorrect 2 ms 3796 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3848 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Incorrect 2 ms 3796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13572 KB Output is correct
2 Correct 34 ms 13068 KB Output is correct
3 Correct 31 ms 11696 KB Output is correct
4 Correct 7 ms 5256 KB Output is correct
5 Correct 6 ms 4692 KB Output is correct
6 Correct 10 ms 6044 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 17 ms 7936 KB Output is correct
9 Correct 29 ms 9996 KB Output is correct
10 Correct 2 ms 3924 KB Output is correct
11 Correct 33 ms 11212 KB Output is correct
12 Correct 46 ms 12052 KB Output is correct
13 Correct 3 ms 3856 KB Output is correct
14 Correct 2 ms 3848 KB Output is correct
15 Correct 2 ms 3796 KB Output is correct
16 Correct 2 ms 3796 KB Output is correct
17 Correct 2 ms 3796 KB Output is correct
18 Correct 2 ms 3796 KB Output is correct
19 Incorrect 2 ms 3796 KB Output isn't correct
20 Halted 0 ms 0 KB -