oj.uz

Submission #241291

# Submission time Handle Problem Language Result Execution time Memory
241291 2020-06-23T17:45:35 Z Mercenary Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 30968 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 150000;
vector<int> adj[maxn * 2] , g[maxn];
int dis[2][maxn * 2];
void dfs(int u  , int dep , int dis[]){
    if(dis[u] != -1){
        dis[u] = dep;
        return;
    }
    dis[u] = dep;
    for(auto & c : adj[u]){
        dfs(c , dep + 1 , dis);
    }
}
#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>

#define MAX_M  1000000
#define MAX_Q  2000

static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;

inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&P));
  for(i=0; i<M; i++)
    my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
  my_assert(1==scanf("%d",&Q));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&G[i]));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&solutions[i]));
}

void answer(int x)
{
  if(answer_count>=Q) {
    printf("Incorrect.  Too many answers.\n");
    exit(0);
  }
  answers[answer_count] = x;
  answer_count++;
}
#endif // LOCAL
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    memset(dis,-1,sizeof dis);;
    for(int i = 0 ; i < M ; ++i){
        g[R[i][0]].pb(R[i][1]);
        g[R[i][1]].pb(R[i][0]);
    }
    for(int i = 0 ; i < N ; ++i){
        g[i].pb(g[i][0]);
        adj[g[i][0] * 2 + (g[g[i][0]][0] == i)].pb(i * 2);
        adj[g[i][1] * 2 + (g[g[i][1]][0] == i)].pb(i * 2 + 1);
    }
    dfs(P * 2 , 0 , dis[0]);
    dfs(P * 2 + 1 , 0 , dis[1]);
    auto check = [&](int u , int st , int dis[] , int& len)->bool{
        if(len == dis[u])return 1;
        if(dis[st] > 0 && dis[u] < len && len % dis[st] == dis[u] % dis[st])return 1;
        return 0;
    };
    for(int i = 0 ; i < Q ; ++i){
        int res = 0;
        for(int j = 0 ; j < N ; ++j){
            if(check(j * 2 , P * 2 , dis[0] , G[i])
               || check(j * 2 , P * 2 + 1 , dis[1] , G[i]))res++;
        }
        answer(res);
    }
}
#ifdef LOCAL
int main()
{
  int correct, i;

  read_input();
  answer_count = 0;
  count_routes(N,M,P,R,Q,G);

  if(answer_count!=Q) {
    printf("Incorrect.  Too few answers.\n");
    exit(0);
  }

  correct = 1;
  for(i=0; i<Q; i++)
    if(answers[i]!=solutions[i])
      correct = 0;
  if(correct)
    printf("Correct.\n");
  else {
    printf("Incorrect.\n");
    printf("Expected: ");
    for(i=0; i<Q; i++)
      printf("%d ",solutions[i]);
    printf("\nReturned: ");
    for(i=0; i<Q; i++)
      printf("%d ",answers[i]);
  }
  return 0;
}
#endif // LOCAL

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13440 KB Output is correct
2 Correct 13 ms 13440 KB Output is correct
3 Correct 13 ms 13312 KB Output is correct
4 Correct 14 ms 13312 KB Output is correct
5 Correct 12 ms 13312 KB Output is correct
6 Correct 13 ms 13440 KB Output is correct
7 Correct 12 ms 13312 KB Output is correct
8 Correct 14 ms 13312 KB Output is correct
9 Correct 16 ms 13568 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13440 KB Output is correct
2 Correct 13 ms 13440 KB Output is correct
3 Correct 13 ms 13312 KB Output is correct
4 Correct 14 ms 13312 KB Output is correct
5 Correct 12 ms 13312 KB Output is correct
6 Correct 13 ms 13440 KB Output is correct
7 Correct 12 ms 13312 KB Output is correct
8 Correct 14 ms 13312 KB Output is correct
9 Correct 16 ms 13568 KB Output is correct
10 Correct 13 ms 13312 KB Output is correct
11 Correct 25 ms 15360 KB Output is correct
12 Correct 45 ms 16888 KB Output is correct
13 Correct 66 ms 30840 KB Output is correct
14 Correct 183 ms 25208 KB Output is correct
15 Correct 228 ms 25592 KB Output is correct
16 Correct 170 ms 22864 KB Output is correct
17 Correct 136 ms 21880 KB Output is correct
18 Correct 48 ms 17016 KB Output is correct
19 Correct 180 ms 25084 KB Output is correct
20 Correct 217 ms 25592 KB Output is correct
21 Correct 171 ms 22648 KB Output is correct
22 Correct 137 ms 21728 KB Output is correct
23 Correct 197 ms 26232 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13440 KB Output is correct
2 Correct 13 ms 13440 KB Output is correct
3 Correct 13 ms 13312 KB Output is correct
4 Correct 14 ms 13312 KB Output is correct
5 Correct 12 ms 13312 KB Output is correct
6 Correct 13 ms 13440 KB Output is correct
7 Correct 12 ms 13312 KB Output is correct
8 Correct 14 ms 13312 KB Output is correct
9 Correct 16 ms 13568 KB Output is correct
10 Correct 13 ms 13312 KB Output is correct
11 Correct 25 ms 15360 KB Output is correct
12 Correct 45 ms 16888 KB Output is correct
13 Correct 66 ms 30840 KB Output is correct
14 Correct 183 ms 25208 KB Output is correct
15 Correct 228 ms 25592 KB Output is correct
16 Correct 170 ms 22864 KB Output is correct
17 Correct 136 ms 21880 KB Output is correct
18 Correct 48 ms 17016 KB Output is correct
19 Correct 180 ms 25084 KB Output is correct
20 Correct 217 ms 25592 KB Output is correct
21 Correct 171 ms 22648 KB Output is correct
22 Correct 137 ms 21728 KB Output is correct
23 Correct 197 ms 26232 KB Output is correct
24 Correct 18 ms 13312 KB Output is correct
25 Correct 1101 ms 15596 KB Output is correct
26 Correct 1995 ms 17016 KB Output is correct
27 Correct 4364 ms 30968 KB Output is correct
28 Execution timed out 5046 ms 25312 KB Time limit exceeded
29 Halted 0 ms 0 KB -