oj.uz

Submission #80036

# Submission time Handle Problem Language Result Execution time Memory
80036 2018-10-18T11:12:15 Z antimirage Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 21168 KB 
#include "gardenlib.h"
#include "garden.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int SZ = 200005;
 
long long n, m, p, q, k[SZ], edges[SZ][2], used[SZ][2], mn[SZ][2], last, go[2], lst, dp[SZ][2][2];
 
void dfs (int v, int type)
{
	used[v][type] = 1;
	
	int to_type;
	
	if (type == 0 || mn[v][1] == -1)
	{
		to_type = (mn[ mn[v][0] ][0] == v ? 1 : 0);
		
		if (mn[v][0] == p)
		{
			if ( to_type == 1 )
				dp[v][type][1] = 1,
				dp[v][type][0] = dp[p][1][0] + 1;
			else
				dp[v][type][0] = 1,
				dp[v][type][1] = dp[p][0][1] + 1;
			
			return;
		}
		if ( to_type == 1 && used[ mn[v][0] ][1] == 0 )
			dfs( mn[v][0], 1);
			
		else if ( used[ mn[v][0] ][0] == 0 )
			dfs( mn[v][0], 0);
			
		dp[v][type][0] = dp[ mn[v][0] ][to_type][0] + 1,
		dp[v][type][1] = dp[ mn[v][0] ][to_type][1] + 1;
	}
	else
	{
		to_type = (mn[ mn[v][1] ][0] == v ? 1 : 0);
		
		if (mn[v][1] == p)
		{
			if ( to_type == 1 )
				dp[v][type][1] = 1,
				dp[v][type][0] = dp[p][1][0] + 1;
			else
				dp[v][type][0] = 1,
				dp[v][type][1] = dp[p][0][1] + 1;
				
			return;
		}
		
		if ( to_type == 1 && used[ mn[v][1] ][1] == 0 )
			dfs( mn[v][1], 1);
		
		else if ( used[ mn[v][1] ][0] == 0 ) 
			dfs( mn[v][1], 0);
		
		dp[v][type][0] = dp[ mn[v][1] ][to_type][0] + 1,
		dp[v][type][1] = dp[ mn[v][1] ][to_type][1] + 1;
	}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	memset(mn, -1, sizeof(mn) );
	n = N, m = M, p = P;
	
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				dp[i][j][k] = 1e12;
	
	for (int i = 0; i < m; i++)
	{
		edges[i][0] = R[i][0], edges[i][1] = R[i][1]; 
		
		if ( mn[ edges[i][0] ][0] == -1 ) mn[ edges[i][0] ][0] = edges[i][1];
		else if ( mn[ edges[i][0] ][1] == -1 ) mn[ edges[i][0] ][1] = edges[i][1];
		
		if ( mn[ edges[i][1] ][0] == -1 ) mn[ edges[i][1] ][0] = edges[i][0];
		else if ( mn[ edges[i][1] ][1] == -1 ) mn[ edges[i][1] ][1] = edges[i][0];
	}
	q = Q;
	for (int i = 0; i < q; i++)
		k[i] = G[i];
	
	dfs(p, 0);
	dfs(p, 1);
 
	for (int i = 0; i < n; i++)
		if (!used[i][0]) dfs(i, 0);
		
	if ( dp[p][0][0] < dp[p][0][1] ) go[0] = 0;
	else go[0] = 1;
	
	if ( dp[p][1][0] < dp[p][1][1] ) go[1] = 0;
	else go[1] = 1;
	
	for (int i = 0; i < q; i++)
	{
		long long ans = 0, sup;
		
		for (int j = 0; j < n; j++)
		{
			if ( min( dp[j][0][0], dp[j][0][1] ) > k[i] ) continue;
			
			if ( dp[j][0][0] < dp[j][0][1] )
			{
				sup = k[i] - dp[j][0][0];
				
				if (sup == 0) {
					ans++;
					continue;
				}
				if (go[0] == 0 && sup % dp[p][0][0] == 0)
					ans++;
				else if (go[0] == 1)
				{
					 if ( go[1] == 0 && (sup % (dp[p][1][0] + dp[p][0][1]) == 0 || sup % (dp[p][1][0] + dp[p][0][1]) == dp[p][0][1] ) )
						ans++;
					 else if ( (sup - dp[p][0][1]) % dp[p][1][1] == 0 )
						ans++;
				}
			}
			else
			{
				sup = k[i] - dp[j][0][1];
				
				if (sup == 0){
					ans++;
					continue;
				}	
				if (go[1] == 1 && sup % dp[p][1][1] == 0)
					ans++;
				else if (go[1] == 0 )
				{
					if (go[0] == 1 && (sup % (dp[p][1][0] + dp[p][0][1]) == 0 || sup % (dp[p][1][0] + dp[p][0][1]) == dp[p][1][0]  ) )
						ans++;
					else if ( (sup - dp[p][1][0]) % dp[p][0][0] == 0 )
						ans++;
				}
			}
		}
		answer(ans);
	}
}
/**
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
**/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3548 KB Output is correct
2 Correct 5 ms 3496 KB Output is correct
3 Correct 5 ms 3576 KB Output is correct
4 Correct 4 ms 3576 KB Output is correct
5 Correct 4 ms 3580 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 4 ms 3552 KB Output is correct
8 Correct 5 ms 3576 KB Output is correct
9 Correct 6 ms 3704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3548 KB Output is correct
2 Correct 5 ms 3496 KB Output is correct
3 Correct 5 ms 3576 KB Output is correct
4 Correct 4 ms 3576 KB Output is correct
5 Correct 4 ms 3580 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 4 ms 3552 KB Output is correct
8 Correct 5 ms 3576 KB Output is correct
9 Correct 6 ms 3704 KB Output is correct
10 Correct 5 ms 3548 KB Output is correct
11 Correct 11 ms 5320 KB Output is correct
12 Correct 20 ms 6748 KB Output is correct
13 Correct 40 ms 17660 KB Output is correct
14 Correct 56 ms 13128 KB Output is correct
15 Correct 58 ms 13432 KB Output is correct
16 Correct 50 ms 11128 KB Output is correct
17 Correct 50 ms 10328 KB Output is correct
18 Correct 21 ms 6932 KB Output is correct
19 Correct 56 ms 13908 KB Output is correct
20 Correct 59 ms 14200 KB Output is correct
21 Correct 51 ms 11728 KB Output is correct
22 Correct 49 ms 11044 KB Output is correct
23 Correct 60 ms 15020 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3548 KB Output is correct
2 Correct 5 ms 3496 KB Output is correct
3 Correct 5 ms 3576 KB Output is correct
4 Correct 4 ms 3576 KB Output is correct
5 Correct 4 ms 3580 KB Output is correct
6 Correct 5 ms 3576 KB Output is correct
7 Correct 4 ms 3552 KB Output is correct
8 Correct 5 ms 3576 KB Output is correct
9 Correct 6 ms 3704 KB Output is correct
10 Correct 5 ms 3548 KB Output is correct
11 Correct 11 ms 5320 KB Output is correct
12 Correct 20 ms 6748 KB Output is correct
13 Correct 40 ms 17660 KB Output is correct
14 Correct 56 ms 13128 KB Output is correct
15 Correct 58 ms 13432 KB Output is correct
16 Correct 50 ms 11128 KB Output is correct
17 Correct 50 ms 10328 KB Output is correct
18 Correct 21 ms 6932 KB Output is correct
19 Correct 56 ms 13908 KB Output is correct
20 Correct 59 ms 14200 KB Output is correct
21 Correct 51 ms 11728 KB Output is correct
22 Correct 49 ms 11044 KB Output is correct
23 Correct 60 ms 15020 KB Output is correct
24 Correct 6 ms 3548 KB Output is correct
25 Correct 140 ms 5628 KB Output is correct
26 Correct 158 ms 7260 KB Output is correct
27 Correct 4586 ms 18560 KB Output is correct
28 Correct 1612 ms 13252 KB Output is correct
29 Correct 4078 ms 13468 KB Output is correct
30 Correct 2654 ms 11216 KB Output is correct
31 Correct 2268 ms 10528 KB Output is correct
32 Correct 200 ms 6696 KB Output is correct
33 Correct 1589 ms 13380 KB Output is correct
34 Correct 3997 ms 13600 KB Output is correct
35 Correct 2664 ms 11352 KB Output is correct
36 Correct 2819 ms 10508 KB Output is correct
37 Correct 1119 ms 14368 KB Output is correct
38 Execution timed out 5034 ms 21168 KB Time limit exceeded