oj.uz

Submission #1032104

# Submission time Handle Problem Language Result Execution time Memory
1032104 2024-07-23T11:38:11 Z VMaksimoski008 Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 16988 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14648 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14428 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 7 ms 14852 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14648 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14428 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 7 ms 14852 KB Output is correct
10 Correct 10 ms 14428 KB Output is correct
11 Execution timed out 5048 ms 16988 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14648 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14428 KB Output is correct
7 Correct 5 ms 14428 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 7 ms 14852 KB Output is correct
10 Correct 10 ms 14428 KB Output is correct
11 Execution timed out 5048 ms 16988 KB Time limit exceeded
12 Halted 0 ms 0 KB -