oj.uz

Submission #552123

# Submission time Handle Problem Language Result Execution time Memory
552123 2022-04-22T13:02:13 Z CSQ31 Dreaming (IOI13_dreaming) C++17
18 / 100
 69 ms 21952 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;
vector<pair<int,int>>adj[MAXN];
bool vis[MAXN];
int dep[MAXN],p[MAXN];
int mn = 2e9,ans = 0;
void dfs(int v,int u){
	vis[v] = 1;
	for(auto x:adj[v]){
		if(x.first != u){
			dfs(x.first,v);
			dep[v] = max(dep[v],dep[x.first] + x.second);
			
		}
	}
}
void get(int v,int u){
	multiset<int,greater<int>>s;
	s.insert(0);
	s.insert(p[v]);
	for(auto x:adj[v]){
		if(x.first == u)continue;
		s.insert(dep[x.first] + x.second);
	}
	int mx = max(p[v],dep[v]);
	mn = min(mx,mn);
	for(auto x:adj[v]){
		if(x.first == u)continue;
		s.erase(s.find(dep[x.first] + x.second));
		p[x.first] = *s.begin() + x.second;
		get(x.first,v);
		s.insert(dep[x.first] + x.second);
	}
	
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i=0;i<M;i++){
		adj[A[i]].push_back({B[i],T[i]});
		adj[B[i]].push_back({A[i],T[i]});
	}
	vector<int>v;
	for(int i=0;i<N;i++){
		if(!vis[i]){
			mn = 2e9;
			dfs(i,-1);
			int c = 0;
			for(auto x:adj[i]){
				ans = max(ans,dep[x.first] + c);
				c = max(c,dep[x.first]);
			}
			get(i,-1);
			v.push_back(mn);
			//cout<<i<<" "<<mn<<'\n';
		}
	}
	//for(int i=0;i<N;i++)cout<<dep[i]<<" ";
	//cout<<'\n';
	//for(int i=0;i<N;i++)cout<<p[i]<<" ";
	//cout<<'\n';
	sort(v.begin(),v.end(),greater<int>());
	if(v.size()>=2)ans = max(ans,v[0] + v[1] + L);
	if(v.size()>=3)ans = max(ans,v[1] + v[2] + 2*L);
	return ans;
}
/*
int main(){
	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);
	
}*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 21952 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 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 21952 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 33 ms 6588 KB Output is correct
2 Correct 30 ms 6548 KB Output is correct
3 Correct 30 ms 6496 KB Output is correct
4 Correct 37 ms 6564 KB Output is correct
5 Correct 26 ms 6468 KB Output is correct
6 Correct 30 ms 7032 KB Output is correct
7 Correct 27 ms 6704 KB Output is correct
8 Correct 26 ms 6504 KB Output is correct
9 Correct 24 ms 6396 KB Output is correct
10 Correct 27 ms 6736 KB Output is correct
11 Correct 2 ms 2664 KB Output is correct
12 Correct 9 ms 3932 KB Output is correct
13 Correct 10 ms 4040 KB Output is correct
14 Correct 10 ms 3940 KB Output is correct
15 Correct 10 ms 3920 KB Output is correct
16 Correct 11 ms 4060 KB Output is correct
17 Correct 8 ms 3536 KB Output is correct
18 Correct 9 ms 4068 KB Output is correct
19 Correct 9 ms 3900 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2664 KB Output is correct
23 Correct 11 ms 3920 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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