oj.uz

Submission #29517

# Submission time Handle Problem Language Result Execution time Memory
29517 2017-07-19T17:25:16 Z kavun Tropical Garden (IOI11_garden) C++14
100 / 100
 4319 ms 44428 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
int nfirst,p,q,f1[300010], f2[300010];
vector <ii> adj[200010];
vector <int> tadj[300010],ans, best[200010];
bool mk1[300010], mk2[300010];
int cycle1, cycle2, flag;

inline int complement(int a)
{
  if(a < nfirst)
    return a + nfirst;
  else
    return a - nfirst;
}

void dfs(int v, int d, bool mk[],int f[], int root)
{
  mk[v] = true;
  f[v] = d;
  for(int i = 0; i < tadj[v].size(); i++)
    {
      int u = tadj[v][i];
      if(u == root){if(flag) cycle2 = d+1; else cycle1 = d+1;}
      if(!mk[u])
	dfs(u,d+1,mk,f,root);
    }
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  nfirst = N;

  for(int i = 0; i < M;i++)
    {
      int u = R[i][0];
      int v = R[i][1];
      if( best[v].size() <= 1 ) best[v].pb( u );
      if( best[u].size() <= 1 ) best[u].pb( v );
    }

    for(int i=0;i<N;i++)
        if( best[i].size() == 1 ) best[i].pb( best[i][0] );

    for(int i = 0; i < N; i++)
      {
	int go = best[i][0];
	int s = (best[go][0] == i);
	if(s)
	  tadj[complement(go)].pb(i);
	else
	  tadj[go].pb(i);
      }
    for(int i = N; i < 2*N; i++)
      {
	int go = best[complement(i)][1];
	int s = (best[go][0] == complement(i));
	if(s)
	  tadj[complement(go)].pb(i);
	else
	  tadj[go].pb(i);
      }

  
  dfs(P,0,mk1,f1,P);
  flag=1;

  for(int i = 0; i < Q; i++)
    {
      int sum = 0;
      for(int v = 0; v < N; v++)      
	{
	  if(!mk1[v]) continue;
	  if(cycle1 && ((G[i] - f1[v]) % cycle1) == 0 && G[i] - f1[v] >= 0)
	    sum++;
	  else 
	    if(G[i] == f1[v])
	      sum++;
	}
      ans.push_back(sum);
    }

  dfs(complement(P),0,mk2,f2,complement(P));

    for(int i = 0; i < Q; i++)
      {
	int sum = 0;
	for(int v = 0; v < N; v++)
	  {
	    if(!mk2[v]) continue;
	    if(cycle2 && ((G[i] - f2[v]) % cycle2) == 0 && G[i] - f2[v] >= 0)
	      sum++;
	    else 
	      if(G[i] == f2[v])
		sum++;
	  }
	ans[i] += sum;
      }

  for(int i = 0;i < Q; i++)
    answer(ans[i]);
}

Compilation message

garden.cpp: In function 'void dfs(int, int, bool*, int*, int)':
garden.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < tadj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17024 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 18 ms 16892 KB Output is correct
4 Correct 17 ms 16824 KB Output is correct
5 Correct 17 ms 16888 KB Output is correct
6 Correct 19 ms 17096 KB Output is correct
7 Correct 17 ms 16820 KB Output is correct
8 Correct 19 ms 16888 KB Output is correct
9 Correct 20 ms 16988 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17024 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 18 ms 16892 KB Output is correct
4 Correct 17 ms 16824 KB Output is correct
5 Correct 17 ms 16888 KB Output is correct
6 Correct 19 ms 17096 KB Output is correct
7 Correct 17 ms 16820 KB Output is correct
8 Correct 19 ms 16888 KB Output is correct
9 Correct 20 ms 16988 KB Output is correct
10 Correct 19 ms 16800 KB Output is correct
11 Correct 28 ms 19020 KB Output is correct
12 Correct 51 ms 20280 KB Output is correct
13 Correct 81 ms 37888 KB Output is correct
14 Correct 202 ms 28752 KB Output is correct
15 Correct 238 ms 29780 KB Output is correct
16 Correct 155 ms 25564 KB Output is correct
17 Correct 142 ms 24916 KB Output is correct
18 Correct 48 ms 20336 KB Output is correct
19 Correct 194 ms 29704 KB Output is correct
20 Correct 238 ms 29796 KB Output is correct
21 Correct 175 ms 25268 KB Output is correct
22 Correct 155 ms 24872 KB Output is correct
23 Correct 203 ms 29668 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17024 KB Output is correct
2 Correct 18 ms 16888 KB Output is correct
3 Correct 18 ms 16892 KB Output is correct
4 Correct 17 ms 16824 KB Output is correct
5 Correct 17 ms 16888 KB Output is correct
6 Correct 19 ms 17096 KB Output is correct
7 Correct 17 ms 16820 KB Output is correct
8 Correct 19 ms 16888 KB Output is correct
9 Correct 20 ms 16988 KB Output is correct
10 Correct 19 ms 16800 KB Output is correct
11 Correct 28 ms 19020 KB Output is correct
12 Correct 51 ms 20280 KB Output is correct
13 Correct 81 ms 37888 KB Output is correct
14 Correct 202 ms 28752 KB Output is correct
15 Correct 238 ms 29780 KB Output is correct
16 Correct 155 ms 25564 KB Output is correct
17 Correct 142 ms 24916 KB Output is correct
18 Correct 48 ms 20336 KB Output is correct
19 Correct 194 ms 29704 KB Output is correct
20 Correct 238 ms 29796 KB Output is correct
21 Correct 175 ms 25268 KB Output is correct
22 Correct 155 ms 24872 KB Output is correct
23 Correct 203 ms 29668 KB Output is correct
24 Correct 19 ms 16860 KB Output is correct
25 Correct 135 ms 18936 KB Output is correct
26 Correct 186 ms 20352 KB Output is correct
27 Correct 1989 ms 37852 KB Output is correct
28 Correct 1403 ms 29348 KB Output is correct
29 Correct 2464 ms 29620 KB Output is correct
30 Correct 1256 ms 25484 KB Output is correct
31 Correct 1419 ms 24672 KB Output is correct
32 Correct 208 ms 20200 KB Output is correct
33 Correct 1377 ms 29088 KB Output is correct
34 Correct 2274 ms 29604 KB Output is correct
35 Correct 1270 ms 25476 KB Output is correct
36 Correct 1976 ms 24728 KB Output is correct
37 Correct 1039 ms 29356 KB Output is correct
38 Correct 4319 ms 44428 KB Output is correct