oj.uz

Submission #888613

# Submission time Handle Problem Language Result Execution time Memory
888613 2023-12-18T02:38:03 Z Muhammad_Aneeq Traffic (IOI10_traffic) C++17
0 / 100
 7 ms 29020 KB 
#include <vector>
#include <algorithm>
using namespace std;
int const MAXN=1e6+10;
vector<int>nei[MAXN]={};
int val[MAXN]={};
vector<int>z;
int dfs(int n,int root,int m=-1)
{
	int ans=0;
	for (auto i:nei[n])
	{
		if (i!=m)
		{
			int x=dfs(i,root,n)+val[i];
			ans+=x;
			if (n==root)
				z.push_back(x);
		}
	}
	return ans;
}
int LocateCentre(int N,int P[1000000],int S[1000000],int D[1000000])
{
	bool w=1;
	for (int i=0;i<N-1;i++)
	{
		nei[S[i]].push_back(D[i]);
		nei[D[i]].push_back(S[i]);
		if (S[i]+1!=D[i])
			w=0;
	}
	if (w==1)
	{
		int f=0;
		for (int i=0;i<N;i++)
			f+=P[i];
		int ans=0,z=2e9+10,cur=0;
		for (int i=0;i<N;i++)
		{
			f-=P[i];
			if (abs(f-cur)<z)
			{
				z=abs(f-cur);
				ans=i;
			}
			cur+=P[i];
		}
		return ans;
	}
	for (int i=0;i<N;i++)
		val[i]=P[i];
	int ans=0,f=2e9+10;
	for (int i=0;i<N;i++)
	{
		dfs(i,i);
		if (z.size()<2)
			z.push_back(0);
		sort(begin(z),end(z));
		if (z.back()-z[0]<f)
		{
			f=z.back()-z[0];
			ans=i;
		}
		z={};
	}
	return ans;
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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