제출 #499662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499662		HappyPacMan	Tropical Garden (IOI11_garden)	C++14	100 / 100	2440 ms	22244 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int MAXN = 150008;
const int INF = 9999999;
vector<pair<int,int> > adj[MAXN];
int graph[2*MAXN], dist[2][2*MAXN], cycle[2][2*MAXN];
 
int dfs(int x, int u){
  if(dist[x][u] != -1) return dist[x][u];
  dist[x][u] = -INF;
  return dist[x][u] = dfs(x,graph[u]) + 1;
}
 
int cyc(int x, int v, int u){
  if(cycle[x][u] != -1) return cycle[x][u];
  cycle[x][u] = u == v ? 0 : -INF;
  return cycle[x][u] = cyc(x,v,graph[u]) + 1;
}
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  for(int i=0;i<M;i++){
    adj[R[i][0]].emplace_back(i,R[i][1]);
    adj[R[i][1]].emplace_back(i,R[i][0]);
  }
  for(int i=0;i<N;i++){
    if(!adj[i].empty()){
      if(adj[i].size() == 1){
        int nxt = adj[i][0].second;
        int rank = adj[i][0].first;
        graph[i<<1] = nxt<<1|(rank == adj[nxt][0].first);
        graph[i<<1|1] = nxt<<1|(rank == adj[nxt][0].first);
      }else{
        int nxt = adj[i][0].second;
        int rank = adj[i][0].first;
        int alter = adj[i][1].second;
        int alter_rank = adj[i][1].first;
        graph[i<<1] = nxt<<1|(rank == adj[nxt][0].first);
        graph[i<<1|1] = alter<<1|(alter_rank == adj[alter][0].first);
      }
    }
  }
  memset(dist,-1,sizeof dist);
  memset(cycle,-1,sizeof cycle);
  dist[0][P<<1] = dist[1][P<<1|1] = 0;
  cyc(0,P<<1,P<<1);
  cyc(1,P<<1|1,P<<1|1);
  for(int i=0;i<(N<<1);i++){
    dfs(0,i);
    dfs(1,i);
  }
  for(int i=0;i<Q;i++){
    int ans = 0;
    for(int j=0;j<N;j++){
      int temp = 0;
      int try1 = dist[0][j<<1];
      int try2 = dist[1][j<<1];
      if(try1 >= 0){
        if(try1 == G[i]) ans++;
        else if(try1 < G[i] && cycle[0][P<<1] > 0){
          int Gtemp = G[i];
          Gtemp -= try1;
          Gtemp %= cycle[0][P<<1];
          if(!Gtemp) temp++;
        }
      }
      if(try2 >= 0){
        if(try2 == G[i]) ans++;
        else if(try2 < G[i] && cycle[1][P<<1|1] > 0){
          int Gtemp = G[i];
          Gtemp -= try2;
          Gtemp %= cycle[1][P<<1|1];
          if(!Gtemp) temp++;
        }
      }
      ans += (temp > 0);
    }
    answer(ans);
  }
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31