oj.uz

Submission #59262

# Submission time Handle Problem Language Result Execution time Memory
59262 2018-07-21T11:11:46 Z TadijaSebez Friend (IOI14_friend) C++11
100 / 100
 129 ms 11972 KB 
#include <stdio.h>
#include <vector>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=100050;
int p[N],q[N],c[N];
vector<pair<int,int> > E[N];
void AddEdge(int u, int v, int w){ E[u].pb(mp(v,w));}
int max(int a, int b){ return a>b?a:b;}
int max(int a, int b, int c){ return max(a,max(b,c));}
void DFS(int u)
{
	p[u]=c[u];q[u]=0;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i].first;
		int w=E[u][i].second;
		DFS(v);
		if(w==0)
		{
			q[u]+=max(q[v],p[v]);
			p[u]+=q[v];
		}
		if(w==1)
		{
			p[u]=max(p[u]+p[v],p[u]+q[v],p[v]+q[u]);
			q[u]+=q[v];
		}
		if(w==2)
		{
			p[u]=max(p[u]+q[v],p[v]+q[u]);
			q[u]+=q[v];
		}
		//printf("%i %i %i:%i %i\n",u-1,v-1,w,p[u],q[u]);
	}
}
int findSample(int n, int co[], int par[], int ty[])
{
	int i;
	for(i=n-1;i;i--) AddEdge(par[i]+1,i+1,ty[i]);
	//for(i=1;i<n;i++) if(ty[i]==2) AddEdge(par[i]+1,i+1,ty[i]);
	//for(i=1;i<n;i++) if(ty[i]==1) AddEdge(par[i]+1,i+1,ty[i]);
	//for(i=1;i<n;i++) if(ty[i]==0) AddEdge(par[i]+1,i+1,ty[i]);
	for(i=1;i<=n;i++) c[i]=co[i-1];
	DFS(1);
	return max(p[1],q[1]);
}

Compilation message

friend.cpp: In function 'void DFS(int)':
friend.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 5 ms 3036 KB Output is correct
3 Correct 5 ms 3092 KB Output is correct
4 Correct 5 ms 3100 KB Output is correct
5 Correct 5 ms 3100 KB Output is correct
6 Correct 5 ms 3120 KB Output is correct
7 Correct 4 ms 3140 KB Output is correct
8 Correct 5 ms 3144 KB Output is correct
9 Correct 4 ms 3188 KB Output is correct
10 Correct 5 ms 3208 KB Output is correct
11 Correct 6 ms 3212 KB Output is correct
12 Correct 4 ms 3236 KB Output is correct
13 Correct 5 ms 3236 KB Output is correct
14 Correct 5 ms 3244 KB Output is correct
15 Correct 6 ms 3252 KB Output is correct
16 Correct 5 ms 3252 KB Output is correct
17 Correct 6 ms 3252 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3252 KB Output is correct
2 Correct 5 ms 3252 KB Output is correct
3 Correct 5 ms 3324 KB Output is correct
4 Correct 6 ms 3324 KB Output is correct
5 Correct 6 ms 3388 KB Output is correct
6 Correct 4 ms 3388 KB Output is correct
7 Correct 5 ms 3388 KB Output is correct
8 Correct 5 ms 3388 KB Output is correct
9 Correct 6 ms 3388 KB Output is correct
10 Correct 5 ms 3388 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3388 KB Output is correct
2 Correct 5 ms 3512 KB Output is correct
3 Correct 5 ms 3512 KB Output is correct
4 Correct 6 ms 3512 KB Output is correct
5 Correct 6 ms 3520 KB Output is correct
6 Correct 6 ms 3548 KB Output is correct
7 Correct 4 ms 3552 KB Output is correct
8 Correct 5 ms 3556 KB Output is correct
9 Correct 4 ms 3564 KB Output is correct
10 Correct 6 ms 3568 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3712 KB Output is correct
2 Correct 4 ms 3720 KB Output is correct
3 Correct 5 ms 3720 KB Output is correct
4 Correct 6 ms 3772 KB Output is correct
5 Correct 5 ms 3856 KB Output is correct
6 Correct 7 ms 3856 KB Output is correct
7 Correct 8 ms 3856 KB Output is correct
8 Correct 5 ms 3856 KB Output is correct
9 Correct 4 ms 3856 KB Output is correct
10 Correct 5 ms 3900 KB Output is correct
11 Correct 5 ms 3900 KB Output is correct
12 Correct 6 ms 3900 KB Output is correct
13 Correct 5 ms 3900 KB Output is correct
14 Correct 5 ms 3900 KB Output is correct
15 Correct 5 ms 3900 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3900 KB Output is correct
2 Correct 5 ms 3900 KB Output is correct
3 Correct 5 ms 3900 KB Output is correct
4 Correct 4 ms 3900 KB Output is correct
5 Correct 5 ms 3900 KB Output is correct
6 Correct 5 ms 3980 KB Output is correct
7 Correct 5 ms 3980 KB Output is correct
8 Correct 5 ms 3980 KB Output is correct
9 Correct 5 ms 3984 KB Output is correct
10 Correct 5 ms 3988 KB Output is correct
11 Correct 5 ms 3988 KB Output is correct
12 Correct 6 ms 3988 KB Output is correct
13 Correct 5 ms 3988 KB Output is correct
14 Correct 6 ms 3988 KB Output is correct
15 Correct 6 ms 3988 KB Output is correct
16 Correct 6 ms 3988 KB Output is correct
17 Correct 5 ms 3988 KB Output is correct
18 Correct 4 ms 3988 KB Output is correct
19 Correct 5 ms 3988 KB Output is correct
20 Correct 4 ms 3988 KB Output is correct
21 Correct 4 ms 3988 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3988 KB Output is correct
2 Correct 6 ms 4044 KB Output is correct
3 Correct 5 ms 4060 KB Output is correct
4 Correct 4 ms 4060 KB Output is correct
5 Correct 5 ms 4060 KB Output is correct
6 Correct 6 ms 4060 KB Output is correct
7 Correct 6 ms 4060 KB Output is correct
8 Correct 5 ms 4060 KB Output is correct
9 Correct 6 ms 4060 KB Output is correct
10 Correct 6 ms 4060 KB Output is correct
11 Correct 6 ms 4060 KB Output is correct
12 Correct 129 ms 9704 KB Output is correct
13 Correct 40 ms 9704 KB Output is correct
14 Correct 52 ms 10844 KB Output is correct
15 Correct 52 ms 11972 KB Output is correct