Submission #1032064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032064		VMaksimoski008	Tropical Garden (IOI11_garden)	C++17	0 / 100	5 ms	14428 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int maxn = 3e5 + 5;

vector<pii> graph_shit[maxn+5];
vector<int> graph[maxn+5];
int n;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N;

    for(int i=0; i<M; i++) {
        graph_shit[R[i][0]].push_back({ i, R[i][1] });
        graph_shit[R[i][1]].push_back({ i, R[i][0] });
    }

    vector<int> in(2*N);
    for(int i=0; i<N; i++) {
        int v = graph_shit[i][0].second;
        graph[i].push_back(v+N); in[v+N] = i;
        // cout << i << " -> " << v+N << '\n';
    }

    for(int i=N; i<2*N; i++) {
        if(graph_shit[i-N].size() == 1) {
            graph[i].push_back(graph_shit[i-N][0].second+N);
        } else {
            if(graph_shit[i-N][0].second == in[i]) graph[i].push_back(graph_shit[i-N][1].second);
            else graph[i].push_back(graph_shit[i-N][0].second);
        }
    }

    for(int i=0; i<Q; i++) {
        int K = G[i], ans = 0;

        for(int j=0; j<N; j++) {
            int curr = j;
            // cout << "START " << j << '\n';
            for(int k=0; k<K&&!graph[curr].empty(); k++) {
                // cout << "to " << graph[curr].back() << '\n';
                curr = graph[curr].back();
            }
            if(curr == P || curr == P + N) ans++;
        }

        answer(ans);
    }
}

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