제출 #65638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65638		mhnd	Tropical Garden (IOI11_garden)	C++14	100 / 100	3508 ms	38264 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

vector<int> g[N],g2[N];
int n,d[2][N],to[N],fr[2],frd[2][2];
bool vis[N];

bool go(int t,int rem){
    if(!rem)return 1;
    if(rem < 0 || fr[t]==-1)return 0;
    if(fr[t] == t)return (rem%frd[t][t])==0;
    rem %= frd[t][!t] + frd[!t][t];
    return go(!t,rem - frd[t][!t]);
}

void bfs(int s,int t){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    d[t][s] = 0;
    while(q.size()){
        int u = q.front();
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i=0;i<(int)g2[u].size();i++){
            int v = g2[u][i];
            if(d[t][v] != -1)continue;
            d[t][v] = d[t][u] + 1;
            q.push(v);
        }
    }
}

void cycle(int s,int t){
    memset(vis,0,sizeof(vis));
    int cur = to[s];
    int d = 1;
    while(!vis[cur]){
        vis[cur] = 1;
        if(cur == s%n){
            fr[t] = 0;
            frd[t][0] = d;
            break;
        }
        if(cur == (s%n)+n){
            fr[t] = 1;
            frd[t][1] = d;
            break;
        }
        d++;
        cur = to[cur];
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N;
    for(int i=0;i<M;i++){
        int u = R[i][0];
        int v = R[i][1];
        if(g[u].size() < 2)g[u].push_back(v);
        if(g[v].size() < 2)g[v].push_back(u);
    }
    for(int i=n;i<2*n;i++){
        g[i] = g[i-n];
        if(g[i].size() == 2)swap(g[i][0],g[i][1]);
    }
    for(int i=0;i<2*n;i++){
        int v = g[i][0];
        if(g[v][0] == i%n)v += n;
        to[i] = v;
        g2[v].push_back(i);
    }
    memset(d,-1,sizeof(d));
    memset(frd,-1,sizeof(frd));
    fr[0] = fr[1] = -1;
    bfs(P,0);
    bfs(P+n,1);
    cycle(P,0);
    cycle(P+n,1);
    for(int i=0;i<Q;i++){
        int dist = G[i];
        int ans = 0;
        for(int j=0;j<n;j++){
            bool o=0,t=0;
            if(d[0][j] != -1){
                int rem = dist - d[0][j];
                o = go(0,rem);
            }
            if(d[1][j] != -1){
                int rem = dist - d[1][j];
                t = go(1,rem);
            }
            ans += o|t;
        }
        answer(ans);
    }
}

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