Submission #1202516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202516		TahirAliyev	Tropical Garden (IOI11_garden)	C++20	0 / 100	7 ms	16136 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;
            if(g[i].size() > 1) nxt[i + n] = g[i][1].second;
            else nxt[i + n] = j + n;
        }
        else nxt[i] = j;
    }
    for(int i = 0; i < 2 * n; i++){
        if(vis[i] || nxt[i] == -1) 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++){
        // cout << i << ' ' << nxt[i] << endl;
        if(nxt[i] != -1) G[nxt[i]].push_back(i);
    }
    if(!cyc[P]){
        sz[0] = 1e9;
        if(nxt[P] != -1) dfs(P, 0, 0);
    } 
    else{
        int a = nxt[P];
        sz[0] = 1;
        while(a != P){
            sz[0]++;
            a = nxt[a];
        } 
        fill(vis, vis + MAX, 0);    
        dfs(P, 0, 0);
    } 
    if(!cyc[P+n]){
        sz[1] = 1e9;
        if(nxt[P+n] != -1) dfs(P+n, 0, 1);
    } 
    else{
        int a = nxt[P+n];
        sz[1] = 1;
        while(a != P+n){
            sz[1]++;
            a = nxt[a];
        } 
        fill(vis, vis + MAX, 0);
        dfs(P+n, 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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31