제출 #241291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241291		Mercenary	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5046 ms	30968 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31