oj.uz

Submission #906242

# Submission time Handle Problem Language Result Execution time Memory
906242 2024-01-13T21:11:30 Z Mathias Dreaming (IOI13_dreaming) C++14
18 / 100
 38 ms 18612 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int INF = 2e9+7;
const int MAXN = 1e5+7;
int xd[MAXN][3];
int ojc[MAXN];
int sum[MAXN];
bool visited[MAXN][3];
vector<int> v;
vector<pair<int,int> > g[MAXN];
int a,b,c,d,m,w,d1,curr,r;
void DFS1(int x,int f,int k){
	visited[x][k]=1;
	for(auto s:g[x]){
		if(s.first==f) continue;
		xd[s.first][k]=max(xd[s.first][k], xd[x][k]+s.second);
		if(xd[s.first][k]>m){
			m=xd[s.first][k];
			d=s.first;
		}
		DFS1(s.first,x,k);
	}
}
void DFS2(int x,int f,int k){
	visited[x][k]=1;
	ojc[x]=f;
	for(auto s:g[x]){
		if(s.first==f) continue;
		xd[s.first][k]=max(xd[s.first][k], xd[x][k]+s.second);
		sum[s.first]=sum[x]+s.second;
		if(xd[s.first][k]>m){
			m=xd[s.first][k];
			d1=s.first;
		}
		DFS2(s.first,x,k);
	}
}
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(visited[i][0]==0){
			m=0; d=i , d1=i;
			DFS1(i,MAXN-1,0);
			m=0;
			DFS2(d,MAXN-1,1);
			r=INF;
			curr=d1;
			while(curr!=MAXN-1){
				if(max(sum[d1]-sum[curr], sum[curr])<r){
					r=max(sum[curr]-sum[d1], sum[curr]);
					w=curr;
				}
				curr=ojc[curr];
			}
			v.push_back(r);
		}
	}
	if(v.size()==1){
		return d;
	}
	else if(v.size()==2){
		a=v[0];
		b=v[1];
		return a+b+L;
	}
	else{
		sort(v.begin(),v.end());
		reverse(v.begin(), v.end());
		a=v[0];
		b=v[1];
		c=v[2];	
		return max(a+b+L,b+c+2*L);
	}
}/*
int main(){
	int A[100], B[100], T[100];
	int n,m,l;
	cin>>n>>m>>l;
	for(int i=0;i<m;i++) cin>>A[i]>>B[i]>>T[i];
	cout<<travelTime(n,m,l,A,B,T)<<'\n';
}
*/

Subtask #1
0 / 14.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 18612 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 15 ms 8796 KB Output is correct
2 Correct 17 ms 8748 KB Output is correct
3 Correct 15 ms 8796 KB Output is correct
4 Correct 15 ms 8796 KB Output is correct
5 Correct 17 ms 8796 KB Output is correct
6 Correct 25 ms 9100 KB Output is correct
7 Correct 15 ms 8924 KB Output is correct
8 Correct 14 ms 8672 KB Output is correct
9 Correct 14 ms 8664 KB Output is correct
10 Correct 15 ms 8920 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 6360 KB Output is correct
13 Correct 5 ms 6616 KB Output is correct
14 Correct 4 ms 6360 KB Output is correct
15 Correct 5 ms 6356 KB Output is correct
16 Correct 5 ms 6104 KB Output is correct
17 Correct 4 ms 5504 KB Output is correct
18 Correct 5 ms 6616 KB Output is correct
19 Correct 5 ms 6196 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 5 ms 6356 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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