Submission #1032104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032104		VMaksimoski008	Tropical Garden (IOI11_garden)	C++17	49 / 100	5048 ms	16988 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<int> 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(R[i][1]);
        graph_shit[R[i][1]].push_back(R[i][0]);
    }

    for(int i=0; i<N; i++) {
        int v = graph_shit[i][0];
        if(graph_shit[v][0] == i) graph[i].push_back(v+N);
        else graph[i].push_back(v);
    }

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

    for(int i=0; i<Q; i++) {
        int ans=0;

        for(int j=0; j<N; j++) {
            int curr = j;
            for(int k=0; k<G[i]&&!graph[curr].empty(); k++) curr = graph[curr].back();
            if(curr == P || curr == P + N) ans++;
        }

        answer(ans);
    }
}

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