oj.uz

Submission #351195

# Submission time Handle Problem Language Result Execution time Memory
351195 2021-01-19T15:28:47 Z Mefarnis Dreaming (IOI13_dreaming) C++14
18 / 100
 59 ms 12908 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
#define fi first
#define se second
#define maxn 100000
#define pb push_back
using namespace std;
typedef pair<int,int> pi;

int tDist,tDist2;
bool mark[maxn];
pi best[maxn][2];
vector<pi> adj[maxn];

void dfs2(int u , int dad , int up) {
	tDist = min(tDist,max(best[u][0].fi,up));
	tDist2 = max(tDist,max(best[u][0].fi,0)+up);
	tDist2 = max(tDist,max(best[u][0].fi,0)+max(best[u][1].fi,0));
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i].fi;
		int e = adj[u][i].se;
		if(v == dad)
			continue;
		if(v == best[u][0].se)
			dfs2(v,u,max(up,best[u][1].fi)+e);
		else
			dfs2(v,u,max(up,best[u][0].fi)+e);
	}
}

int dfs1(int u , int dad) {
	mark[u] = true;
	int deg = adj[u].size();
	best[u][0] = best[u][1] = pi(-1,-1);
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i].fi;
		int e = adj[u][i].se;
		if(v == dad)
			continue;
		int len = dfs1(v,u) + e;
		if(len >= best[u][0].fi) {
			best[u][1] = best[u][0];
			best[u][0] = pi(len,v);
		}
		else if(len >= best[u][1].fi)
			best[u][1] = pi(len,v);
	}
	return max(best[u][0].fi,0);
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	for( int i = 0 ; i < m ; i++ ) {
		adj[a[i]].pb(pi(b[i],t[i]));
		adj[b[i]].pb(pi(a[i],t[i]));
	}
	memset(mark,false,sizeof(mark));
	vector<int> dists;
	tDist2 = 0;
	for( int i = 0 ; i < n ; i++ )
		if(!mark[i]) {
			dfs1(i,-1);
			tDist = INT_MAX;
			dfs2(i,-1,0);
			//printf("tDist = %d\n",tDist);
			dists.pb(tDist);
		}
	int ans;
	int k = dists.size();
	if(k == 1)
		ans = tDist2;
	else if(k == 2)
		ans = max(dists[0]+dists[1]+l,tDist2);
	else {
		sort(dists.begin(),dists.end());
		ans = max(dists[k-1]+dists[k-2]+l,dists[k-2]+dists[k-3]+2*l);
		ans = max(ans,tDist2);
	}
	return ans;
}

/*
int main() {
	int n = 12;
	int m = 8;
	int l = 2;
	int a[8] = {0,8,2,5,5,1,1,10};
	int b[8] = {8,2,7,11,1,3,9,6};
	int t[8] = {4,2,4,3,7,1,5,3};
	int ans = travelTime(n,m,l,a,b,t);
	printf("%d\n",ans);
	return 0;
}
*/

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 12908 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 26 ms 6896 KB Output is correct
2 Correct 32 ms 7020 KB Output is correct
3 Correct 28 ms 6896 KB Output is correct
4 Correct 26 ms 6892 KB Output is correct
5 Correct 27 ms 6892 KB Output is correct
6 Correct 29 ms 7408 KB Output is correct
7 Correct 26 ms 7152 KB Output is correct
8 Correct 24 ms 6896 KB Output is correct
9 Correct 25 ms 6892 KB Output is correct
10 Correct 27 ms 7020 KB Output is correct
11 Correct 2 ms 2924 KB Output is correct
12 Correct 6 ms 4840 KB Output is correct
13 Correct 7 ms 4968 KB Output is correct
14 Correct 7 ms 4836 KB Output is correct
15 Correct 6 ms 4840 KB Output is correct
16 Correct 6 ms 4836 KB Output is correct
17 Correct 6 ms 4836 KB Output is correct
18 Correct 8 ms 4968 KB Output is correct
19 Correct 6 ms 4836 KB Output is correct
20 Correct 2 ms 2796 KB Output is correct
21 Correct 2 ms 2796 KB Output is correct
22 Correct 2 ms 2796 KB Output is correct
23 Correct 6 ms 4836 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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