Submission #1202652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202652		TahirAliyev	Tropical Garden (IOI11_garden)	C++20	100 / 100	86 ms	41740 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define all(v) v.begin(), v.end()

const int MAX = 3e5 + 5;
int n, m, p, q;
vector<pii> g[MAX];
int nxt[MAX];
vector<int> G[MAX];
int vis[MAX], cyc[MAX];
int H[MAX][2], sz[2];

void dfs(int node, int h, int t){
    vis[node] = 1;
    if(node < n) H[h][t]++;
    for(int to : G[node]){
        if(vis[to]) continue;
        dfs(to, h + 1, t);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int QQ[]){
    n = N, m = M, p = P, q = Q;
    for(int i = 0; i < M; i++){
        g[R[i][0]].push_back({i, R[i][1]});
        g[R[i][1]].push_back({i, R[i][0]});
    }
    for(int i = 0; i < n; i++) sort(all(g[i]));
    for(int i = 0; i < 2 * n; i++) nxt[i] = -1;
    for(int i = 0; i < n; i++){
        int j = g[i][0].second;
        if(g[j][0].second == i) nxt[i] = j + n;
        else nxt[i] = j;
        if(g[i].size() > 1){
            int k = g[i][1].second;
            if(g[k][0].second == i) nxt[i + n] = k + n;
            else nxt[i + n] = k;
        } 
        else{
            if(g[j][0].second == i) nxt[i + n] = j + n;
            else nxt[i + n] = j;
        } 
    }
    for(int i = 0; i < 2 * n; i++){
        if(vis[i]) continue;
        int a = i;
        while(!vis[a]){
            vis[a] = i + 1;
            a = nxt[a];
        }
        if(vis[a] != i + 1) continue;
        int b = nxt[a];
        cyc[a] = 1;
        while(b != a){
            cyc[b] = 1;
            b = nxt[b];
        }
    }
    for(int i = 0; i < 2 * n; i++){
        G[nxt[i]].push_back(i);
    }
    fill(vis, vis + MAX, 0);
    if(!cyc[p]){
        sz[0] = 1e9;
        dfs(p, 0, 0);
    } 
    else{
        int a = nxt[p];
        sz[0] = 1;
        while(a != p){
            sz[0]++;
            a = nxt[a];
        }
        dfs(p, 0, 0);
    } 
    fill(vis, vis + MAX, 0);
    p += n;
    if(!cyc[p]){
        sz[1] = 1e9;
        dfs(p, 0, 1);
    } 
    else{
        int a = nxt[p];
        sz[1] = 1;
        while(a != p){
            sz[1]++;
            a = nxt[a];
        }
        dfs(p, 0, 1);
    }
    for(int z = 0; z < q; z++){
        int k = QQ[z];
        int ans = 0;
        for(int i = k % sz[0]; i <= min(MAX-1, k); i += sz[0]){
            ans += H[i][0];
        }
        for(int i = k % sz[1]; i <= min(MAX-1, k); i += sz[1]){
            ans += H[i][1];
        }
        answer(ans);        
    }
}

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