제출 #164698

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

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M, P, Q;
int *G;
vector<int> adj2[MAXN+10];
vector<int> adj[MAXN+10];

int ans[MAXN+10];
int cnt[MAXN+10], cyc=-1;
int dep[MAXN+10];

void dfs(int now, int depth)
{
    //printf("%d\n", now);
    dep[now]=depth;
    for(auto nxt : adj[now])
    {
        if(dep[nxt]!=-1)
        {
            cyc=depth+1;
            continue;
        }
        dfs(nxt, depth+1);
    }
}

void count_routes(int _N, int _M, int _P, int R[][2], int _Q, int *_G)
{
    int i, j;
    N=_N; M=_M; P=_P; Q=_Q; G=_G;

    for(i=0; i<M; i++)
    {
        int u=R[i][0], v=R[i][1];
        adj2[u].push_back(v);
        adj2[v].push_back(u);
    }

    for(i=0; i<N; i++)
    {
        int nxt=adj2[i][0];
        if(adj2[nxt][0]==i) adj[nxt+N].push_back(i);//, printf("E%d %d\n", nxt+N, i);
        else adj[nxt].push_back(i);//, printf("E%d %d\n", nxt, i);
    }

    for(i=0; i<N; i++)
    {
        int nxt;
        if(adj2[i].size()==1) nxt=adj2[i][0];
        else nxt=adj2[i][1];

        if(adj2[nxt][0]==i) adj[nxt+N].push_back(i+N);//, printf("E%d %d\n", nxt+N, i+N);
        else adj[nxt].push_back(i+N);//, printf("E%d %d\n", nxt, i+N);
    }

    memset(cnt, 0, sizeof(cnt));
    memset(dep, -1, sizeof(dep));
    cyc=-1;
    dfs(P, 0);
    for(i=0; i<N; i++) cnt[dep[i]]++;

    for(i=0; i<Q; i++)
    {
        if(cyc==-1)
        {
            if(G[i]<2*N) ans[i]+=cnt[G[i]];
        }
        else
        {
            for(j=G[i]%cyc; j<2*N && j<=G[i]; j+=cyc) ans[i]+=cnt[j];
        }
    }

    //printf("!%d\n", cyc);

    memset(cnt, 0, sizeof(cnt));
    memset(dep, -1, sizeof(dep));
    cyc=-1;
    dfs(P+N, 0);
    for(i=0; i<N; i++) cnt[dep[i]]++;

    for(i=0; i<Q; i++)
    {
        if(cyc==-1)
        {
            if(G[i]<2*N) ans[i]+=cnt[G[i]];
        }
        else
        {
            for(j=G[i]%cyc; j<2*N && j<=G[i]; j+=cyc) ans[i]+=cnt[j];
        }
    }

    //printf("!%d\n", cyc);
    for(i=0; i<Q; i++) answer(ans[i]);
}

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