oj.uz

Submission #374222

# Submission time Handle Problem Language Result Execution time Memory
374222 2021-03-06T23:11:07 Z ijxjdjd Tropical Garden (IOI11_garden) C++14
100 / 100
 2759 ms 25008 KB 
#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int MAXN = (int)(150000);
const int INF = (int)(2e9);
vector<int> revadj[2*MAXN];
int first[MAXN];
int second[MAXN];
int to[2*MAXN];
bool seen[2*MAXN];
int dist[2*MAXN][2];
int oppose(int a, int r[2]) {
    if (r[0] == a) {
        return r[1];
    }
    return r[0];
}
int checkLoop(int start) {
    memset(seen, 0, sizeof(seen));
    int ori = start;
    int cnt = 1;
    seen[start] = true;
    while (!seen[to[start]]) {
        cnt++;
        start = to[start];
        seen[start] = true;
    }
    start = to[start];
    if (ori != start) {
        return INF;
    }
    else {
        return cnt;
    }
}
void mdist(int start) {
    int id = start&1;
    for (int i = 0; i < 2*MAXN; i++){
        dist[i][id] = INF;
    }
    deque<int> deq;
    deq.push_back(start);
    dist[start][id] = 0;
    while (deq.size()) {
        int n = deq.front();
        deq.pop_front();
        for (int e : revadj[n]) {
            if (dist[e][id] > dist[n][id] + 1) {
                dist[e][id] = dist[n][id]+1;
                deq.push_back(e);
            }
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    fill(all(first), -1);
    fill(all(second), -1);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 2; j++) {
            if (first[R[i][j]] == -1) {
                first[R[i][j]] = i;
            }
            else if (second[R[i][j]] == -1) {
                second[R[i][j]] = i;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        int fv = oppose(i, R[first[i]]);
        if (first[fv] == first[i]) {
            to[2*i] = 2*fv+1;
        }
        else {
            to[2*i] = 2*fv;
        }
        if (second[i] != -1) {
            int sv = oppose(i, R[second[i]]);
            if (first[sv] == second[i]) {
                to[2*i+1] = 2*sv+1;
            }
            else {
                to[2*i+1] = 2*sv;
            }
        }
        else {
            to[2*i+1] = to[2*i];
        }
        revadj[to[2*i]].push_back(2*i);
        revadj[to[2*i+1]].push_back(2*i+1);
    }
    int lp[2];
    lp[0] = checkLoop(2*P);
    lp[1] = checkLoop(2*P+1);
    mdist(2*P);
    mdist(2*P+1);
    for (int iter = 0; iter < Q; iter++) {
        int k = G[iter];
        int cnt = 0;
        for (int i =0; i < 2*N; i+=2) {
            bool good = false;
            if (dist[i][0] <= k && (k-dist[i][0])%lp[0] == 0) {
                good = true;
            }
            if (dist[i][1] <= k && (k-dist[i][1])%lp[1] == 0) {
                good = true;
            }
            cnt += good;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11244 KB Output is correct
2 Correct 7 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 7 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 7 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 10 ms 11372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11244 KB Output is correct
2 Correct 7 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 7 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 7 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 10 ms 11372 KB Output is correct
10 Correct 8 ms 11244 KB Output is correct
11 Correct 16 ms 12780 KB Output is correct
12 Correct 28 ms 13804 KB Output is correct
13 Correct 45 ms 18944 KB Output is correct
14 Correct 94 ms 19504 KB Output is correct
15 Correct 129 ms 20076 KB Output is correct
16 Correct 88 ms 17900 KB Output is correct
17 Correct 84 ms 17388 KB Output is correct
18 Correct 29 ms 13932 KB Output is correct
19 Correct 97 ms 19712 KB Output is correct
20 Correct 125 ms 20076 KB Output is correct
21 Correct 88 ms 17968 KB Output is correct
22 Correct 84 ms 17424 KB Output is correct
23 Correct 91 ms 20332 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11244 KB Output is correct
2 Correct 7 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 7 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 7 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 10 ms 11372 KB Output is correct
10 Correct 8 ms 11244 KB Output is correct
11 Correct 16 ms 12780 KB Output is correct
12 Correct 28 ms 13804 KB Output is correct
13 Correct 45 ms 18944 KB Output is correct
14 Correct 94 ms 19504 KB Output is correct
15 Correct 129 ms 20076 KB Output is correct
16 Correct 88 ms 17900 KB Output is correct
17 Correct 84 ms 17388 KB Output is correct
18 Correct 29 ms 13932 KB Output is correct
19 Correct 97 ms 19712 KB Output is correct
20 Correct 125 ms 20076 KB Output is correct
21 Correct 88 ms 17968 KB Output is correct
22 Correct 84 ms 17424 KB Output is correct
23 Correct 91 ms 20332 KB Output is correct
24 Correct 10 ms 11244 KB Output is correct
25 Correct 93 ms 12780 KB Output is correct
26 Correct 125 ms 14188 KB Output is correct
27 Correct 2512 ms 19180 KB Output is correct
28 Correct 882 ms 19724 KB Output is correct
29 Correct 2757 ms 20144 KB Output is correct
30 Correct 1619 ms 18140 KB Output is correct
31 Correct 1594 ms 17592 KB Output is correct
32 Correct 133 ms 14060 KB Output is correct
33 Correct 895 ms 19948 KB Output is correct
34 Correct 2759 ms 20076 KB Output is correct
35 Correct 1769 ms 17900 KB Output is correct
36 Correct 1885 ms 17592 KB Output is correct
37 Correct 710 ms 20388 KB Output is correct
38 Correct 2201 ms 25008 KB Output is correct