oj.uz

Submission #676937

# Submission time Handle Problem Language Result Execution time Memory
676937 2023-01-01T16:37:09 Z penguin133 Dreaming (IOI13_dreaming) C++17
18 / 100
 44 ms 17228 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
 
//#define int long long
typedef int ll;
#define pi pair<int, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
 
int vis[100005];
vector<pi>v[100005], adj[100005];
ll maxi = -1e9, pos;
vector<int> trav;
void dfs(int x, ll cur){
	if(vis[x])return;
	vis[x] = 1;
	trav.push_back(x);
	if(cur > maxi)maxi = cur, pos = x;
	for(auto [i, j] : v[x])dfs(i, cur + j);
}
 
void diam(int x, int p, ll cur){
  vis[x] = 1;
	if(cur > maxi)maxi = cur, pos = x;
	for(auto [i, j] : v[x])if(i != p)diam(i, x, cur + j);
}
 
vector<pi> mids; vector<int> path;
 
void find(int cur, int tgt, int p){
	trav.push_back(cur);
	if(cur == tgt){
		path = trav;
		return;
	}
	for(auto [i, j] : v[cur])if(i != p)find(i, tgt, cur);
	trav.pop_back();
}
 
ll mx;
vector<pi>dist;
void recur(int x, int p, ll cur){
	mx = max(mx, cur);
	for(auto [i, j] : v[x])if(i != p)recur(i, x, cur + j);
}
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	
	for(int i=0;i<M;i++)v[A[i]].push_back({B[i], T[i]}), v[B[i]].push_back({A[i], T[i]});
	for(int i=0;i<N;i++){
		if(!vis[i]){
			maxi = -1e9;
			diam(i, -1, 0);
			int pos2 = pos;
			maxi = -1e9;
			diam(pos, -1, 0);
			//cerr << pos << " " << pos2 << '\n';
			ll cur = 0;
			ll mn = INT_MAX; 
			find(pos2, pos, -1);
			int cent = path[0];
			trav.clear();
			for(int j=0;j<(int)path.size();j++){
				mx = max(cur, maxi - cur);
				for(auto [a, b] : v[path[j]]){
					if((!j || path[j-1] != a) && (j == (int)path.size() - 1 || path[j+1] != a))recur(a, path[j], b);
					if(j < (int)path.size() - 1 && a == path[j+1])cur += b;
				}
				if(mn > mx)mn = mx, cent = path[j];
			}
			//cerr << cent << '\n';
			mids.push_back({cent, mn});
			dist.push_back({mn, cent});
		}
	}
	//for(auto i : mids)cerr << i << " ";
	//cerr << '\n';
	sort(dist.begin(), dist.end(), greater<pi>());
	ll mini = INT_MAX;
	for(auto [i, j] : mids){
		pi pos = {-1, -1}, pos2 = {-1, -1};
		for(int k=0;k<(int)dist.size();k++){
			if(dist[k].se == i)continue;
			if(pos.fi == -1)pos = dist[k];
			else {
				pos2 = dist[k];
				break;
			}
		}
		if(pos.fi == -1)mini = min(mini, j);
		else if(pos2.fi == -1)mini = min(mini, j + L + pos.fi);
		else mini = min(mini, max(j + L + pos.fi, 2 * L + pos.fi + pos2.fi));
	}
	return mini;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9224 KB Output is correct
2 Correct 25 ms 9232 KB Output is correct
3 Correct 29 ms 9296 KB Output is correct
4 Correct 35 ms 9228 KB Output is correct
5 Correct 24 ms 9204 KB Output is correct
6 Correct 27 ms 10032 KB Output is correct
7 Correct 27 ms 9484 KB Output is correct
8 Correct 25 ms 9172 KB Output is correct
9 Correct 27 ms 9196 KB Output is correct
10 Correct 25 ms 9392 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 11 ms 7032 KB Output is correct
13 Correct 12 ms 7104 KB Output is correct
14 Correct 12 ms 7032 KB Output is correct
15 Correct 11 ms 7032 KB Output is correct
16 Correct 11 ms 7032 KB Output is correct
17 Correct 10 ms 7032 KB Output is correct
18 Correct 12 ms 7240 KB Output is correct
19 Correct 11 ms 7104 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5012 KB Output is correct
23 Correct 11 ms 7112 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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