제출 #797228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797228		Khizri	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	2292 ms	36812 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=4e5+5;
int n,m,fin,k,best[mxn][3],go[mxn],color[mxn],color2[mxn],dis[mxn],dis2[mxn],sz=-1,sz2=-1;
vector<int>vt[mxn];
void dfs(int u,int dep){
    color[u]=1;
    dis[u]=dep;
    for(int v:vt[u]){
        if(!color[v]){
            dfs(v,dep+1);
        }
        else if(color[v]==1&&v==fin){
            sz=dep+1;
        }
    }
    color[u]=2;
}
void dfs2(int u,int dep){
    color2[u]=1;
    dis2[u]=dep;
    for(int v:vt[u]){
        if(!color2[v]){
            dfs2(v,dep+1);
        }
        else if(color2[v]==1&&v==fin+n){
            sz2=dep+1;
        }
    }
    color2[u]=2;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n=N,m=M,fin=P+1;
    for(int i=0;i<m;i++){
        int u=R[i][0]+1,v=R[i][1]+1;
        if(!best[u][0]){
            best[u][0]=v;
        }
        else if(!best[u][1]){
            best[u][1]=v;
        }
        if(!best[v][0]){
            best[v][0]=u;
        }
        else if(!best[v][1]){
            best[v][1]=u;
        }
    }
    for(int i=1;i<=n;i++){
        if(!best[i][1]){
            best[i][1]=best[i][0];
        }
    }
    for(int u=1;u<=n;u++){
        int x=best[u][0],y=best[u][1];
        if(best[x][0]==u){
            go[u]=x+n;
        }
        else{
            go[u]=x;
        }
        if(best[y][0]==u){
            go[u+n]=y+n;
        }
        else{
            go[u+n]=y;
        }
    }
    for(int i=1;i<=2*n;i++){
        vt[go[i]].pb(i);
    }
    for(int i=1;i<=2*n;i++){
        dis[i]=1e9+7;
        dis2[i]=1e9+7;
    }
    dfs(fin,0);
    dfs2(fin+n,0);
    for(int id=0;id<Q;id++){
        k=G[id];
        int ans=0;
        for(int i=1;i<=n;i++){
            if(dis[i]==k||dis2[i]==k){
                ans++;
            }
            else{
                int x=k-dis[i],y=k-dis2[i];
                if(x>0&&sz>0&&x%sz==0){
                    ans++;
                }
                else if(y>0&&sz2>0&&y%sz2==0){
                    ans++;
                }
            }
        }
        answer(ans);
    }
}

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