Submission #1279443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279443		Nipphitch	Tropical Garden (IOI11_garden)	C++20	100 / 100	1613 ms	41544 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
const int MXN=3e5+10;

int n,m,st,nxt[2][MXN],d[2][MXN],cycle[2];
vector <pii> adj2[MXN];
vector <int> adj[MXN];

void dfs(int u,int s,int d_u){
    d[s][u]=d_u;
    for(int v:adj[u]){
        if(v==s*n+st) cycle[s]=d_u+1;
        if(d[s][v]==-1) dfs(v,s,d_u+1);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n=N,m=M,st=P;
    cycle[0]=cycle[1]=-1;
    memset(d,-1,sizeof(d));
    for(int i=0;i<m;i++){
        adj2[R[i][0]].push_back({i,R[i][1]});
        adj2[R[i][1]].push_back({i,R[i][0]});
    }
    for(int i=0;i<n;i++){
        sort(adj2[i].begin(),adj2[i].end());
        nxt[0][i]=adj2[i][0].second;
        nxt[1][i]=adj2[i][adj2[i].size()>1].second;
    }
    for(int i=0;i<n;i++){
        bool ok=(i==nxt[0][nxt[0][i]]);
        adj[n*ok+nxt[0][i]].push_back(i);
        ok=(i==nxt[0][nxt[1][i]]);
        adj[n*ok+nxt[1][i]].push_back(i+n);
    }
    dfs(st,0,0);
    dfs(st+n,1,0);
    for(int i=0;i<Q;i++){
        int cnt=0;
        for(int u=0;u<n;u++){
            for(int s=0;s<2;s++){
                bool ok=true;
                if(d[s][u]==-1) ok=false;
                else if(cycle[s]==-1) ok=(d[s][u]==G[i]);
                else{
                    int rem=G[i]-d[s][u];
                    ok=(rem>=0 && rem%cycle[s]==0);
                }
                if(ok){
                    cnt++;
                    break;
                }
            }
        }
        answer(cnt);
    }
}

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