Submission #1279207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279207		Nipphitch	Tropical Garden (IOI11_garden)	C++20	100 / 100	1599 ms	40048 KiB

garden

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

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

void dfs(int u,int state,int d_u){
    d[state][u]=d_u;
    vis[state][u]=true;
    for(int v:adj[u]){
        if(v==state*n+st) cycle[state]=d_u+1;
        if(!vis[state][v]) dfs(v,state,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;
    memset(d,-1,sizeof(d));
    cycle[0]=cycle[1]=-1;
    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].s;
        nxt[1][i]=adj2[i][adj2[i].size()>1].s;
    }
    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 state=0;state<2;state++){    
                bool ok=true;
                if(d[state][u]==-1) ok=false;
                else if(cycle[state]==-1) ok=(d[state][u]==G[i]);
                else{
                    int rem=G[i]-d[state][u];
                    ok=(rem%cycle[state]==0 && rem>=0);
                }
                if(ok){
                    cnt++;
                    break;
                }
            }
        }
        answer(cnt);
    }
}

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