Submission #1162668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162668		spongb	Tropical Garden (IOI11_garden)	C++20	100 / 100	1385 ms	29800 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
#define v vector
#define pii pair<int,int>
#define ll long long
#define pli pair<long long, int>
#define fi first
#define se second

using namespace std;

const int LIMIT = 29;


void dfs(v<v<int>> &adj, int node, int dist, v<int> &dists) {
    if (dists[node] != -1) return;
    dists[node] = dist;
    for (int nex : adj[node]) {
        dfs(adj, nex, dist + 1, dists);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    v<int> first(N, -1), second(N, -1), next(2 * N, -1);
    
    for (int i = 0; i < M; i++) {
        int a = R[i][0], b = R[i][1];
        if (first[a] == -1) first[a] = b;
        else if (second[a] == -1) second[a] = b;
        if (first[b] == -1) first[b] = a;
        else if (second[b] == -1) second[b] = a;
    }
    
    for (int i = 0; i < N; i++) {
        if (second[i] == -1) second[i] = first[i];
    }
    
    for (int i = 0; i < N; i++) {
        next[2 * i] = (first[first[i]] == i) ? first[i] * 2 + 1 : first[i] * 2;
        next[2 * i + 1] = (first[second[i]] == i) ? second[i] * 2 + 1 : second[i] * 2;
    }
    
    
    int p_cycle0 = 1e9 + 100, p_cycle1 = 1e9 + 100;
    
    int cur = 2 * P;
    for (int i = 0; i < 2 * N; i++) {
        cur = next[cur];
        if (cur == 2 * P) {
            p_cycle0 = i + 1;
            break;
        }
    }
    
    cur = 2 * P + 1;
    for (int i = 0; i < 2 * N; i++) {
        cur = next[cur];
        if (cur == 2 * P + 1) {
            p_cycle1 = i + 1;
            break;
        }
    }
    
    v<v<int>> adj(2 * N);
    for (int i = 0; i < 2 * N; i++) {
        adj[next[i]].push_back(i);
    }
    
    v<int> dists0(2 * N, -1), dists1(2 * N, -1);
    dfs(adj, 2 * P, 0, dists0);
    dfs(adj, 2 * P + 1, 0, dists1);
    
    for (int i = 0; i < Q; i++) {
        int K = G[i], count = 0;
        for (int j = 0; j < N; j++) {
            if ((dists0[2 * j] != -1 && dists0[2 * j] <= K && (K - dists0[2 * j]) % p_cycle0 == 0) ||
                (dists1[2 * j] != -1 && dists1[2 * j] <= K && (K - dists1[2 * j]) % p_cycle1 == 0)) {
                count++;
            }
        }
        answer(count);
    }
}

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