제출 #1029110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029110		idas	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	100 / 100	1247 ms	35604 KiB

garden

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

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;

const int MxN=150001, INF=1e9;
int mn[2*MxN], mx[2*MxN], nxt[2*MxN], dist[2*MxN][2], cyc[2];
vi prv[2*MxN];
bool v[2*MxN];

int cyc_find(int u, int st)
{
    if(v[u]){
        if(u==st) return 0;
        else return -1;
    }
    v[u]=true;
    int x=nxt[u];
    int k=cyc_find(x, st);
    if(k==-1) return -1;
    else return k+1;
}

void calc_dist(int u, int in)
{
    for(auto x : prv[u]){
        if(dist[x][in]==-1){
            dist[x][in]=dist[u][in]+1;
            calc_dist(x, in);
        }
    }
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
    FOR(i, 0, n)
    {
        mn[i]=mn[i+n]=-1;
        mx[i]=mx[i+n]=-1;
        nxt[i]=nxt[i+n]=-1;
    }

    FOR(i, 0, m)
    {
        int a=r[i][0], b=r[i][1];

        if(mn[a]==-1) mn[a]=mn[a+n]=b;
        else if(mx[a]==-1) mx[a]=mx[a+n]=b;

        if(mn[b]==-1) mn[b]=mn[b+n]=a;
        else if(mx[b]==-1) mx[b]=mx[b+n]=a;
    }

    FOR(i, 0, n)
    {
        int x=mn[i];
        if(mx[x]==-1){
            nxt[i]=x;
        }
        else if(mn[x]==i){
            nxt[i]=x+n;
        }
        else{
            nxt[i]=x;
        }
    }

    FOR(i, n, 2*n)
    {
        if(mx[i]==-1) continue;

        int x=mx[i];
        if(mx[x]==-1){
            nxt[i]=x;
        }
        else if(mn[x]==i-n){
            nxt[i]=x+n;
        }
        else{
            nxt[i]=x;
        }
    }

    FOR(i, 0, 2*n)
    {
        dist[i][0]=dist[i][1]=-1;
        if(nxt[i]!=-1) prv[nxt[i]].pb(i);
    }

    cyc[0]=cyc_find(p, p);
    FOR(i, 0, 2*n) v[i]=false;
    cyc[1]=cyc_find(p+n, p+n);

    dist[p][0]=0; calc_dist(p, 0);
    dist[p+n][1]=0; calc_dist(p+n, 1);

    FOR(i, 0, q)
    {
        int ans=0;
        FOR(j, 0, n)
        {
            FOR(k, 0, 2)
            if(dist[j][k]!=-1){
                if(cyc[k]==-1){
                    if(dist[j][k]==g[i]) ans++;
                }
                else if(g[i]>=dist[j][k] && (g[i]-dist[j][k])%cyc[k]==0) ans++;
            }
        }
        answer(ans);
    }
}

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