oj.uz

Submission #121135

# Submission time Handle Problem Language Result Execution time Memory
121135 2019-06-26T07:02:28 Z 송준혁(#2942) Tropical Garden (IOI11_garden) C++14
100 / 100
 211 ms 42060 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define INF (1<<30)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, P, Q, C1, C2;
int O[202020], D1[202020], D2[202020];
int cnt1[1010101], cnt2[1010101];
vector<pii> G[202020];
vector<int> radj[303030];
int adj[303030];
bool visit[303030];

void dfs1(int u, int d){
    if (visit[u]) return;
    visit[u] = true;
    if (u < N) cnt1[d]++;
    for (int v : radj[u]) dfs1(v, d+1);
}

void dfs2(int u, int d){
    if (visit[u]) return;
    visit[u] = true;
    if (u < N) cnt2[d]++;
    for (int v : radj[u]) dfs2(v, d+1);
}

int cyc1(int u, int d){
    if (visit[u]) return -1;
    if (u == P) return d;
    visit[u] = true;
    return cyc1(adj[u], d+1);
}

int cyc2(int u, int d){
    if (visit[u]) return -1;
    if (u == P+N) return d;
    visit[u] = true;
    return cyc2(adj[u], d+1);
}

void count_routes(int n, int m, int p, int R[][2], int q, int d[]){
    N=n, M=m, P=p, Q=q;
    for (int i=0; i<M; i++){
        G[R[i][0]].push_back(pii(i, R[i][1]));
        G[R[i][1]].push_back(pii(i, R[i][0]));
    }
    for (int i=0; i<N; i++){
        int Min=INF;
        for (pii j : G[i]) if (j.first < Min) Min = j.first, O[i] = j.second;
    }
    for (int i=0; i<N; i++){
        if (O[O[i]] != i) {
            radj[O[i]].push_back(i);
            adj[i] = O[i];
        }
        else {
            radj[O[i]+N].push_back(i);
            adj[i] = O[i]+N;
        }
        int Min=INF, u=-1;
        for (pii j : G[i]) if (j.first < Min) {
            if (j.second == O[i]) continue;
            Min = j.first, u = j.second;
        }
        if (u != -1){
            if (O[u] == i) {
                radj[u+N].push_back(i+N);
                adj[i+N] = u+N;
            }
            else {
                radj[u].push_back(i+N);
                adj[i+N] = u;
            }
        }
        else {
            if (O[O[i]] == i){
                radj[O[i]+N].push_back(i+N);
                adj[i+N] = O[i]+N;
            }
            else{
                radj[O[i]].push_back(i+N);
                adj[i+N] = O[i];
            }
        }
    }
    memset(D1, -1, sizeof D1);
    dfs1(P, 0);
    memset(visit, false, sizeof visit);
    dfs2(P+N, 0);
    memset(visit, false, sizeof visit);
    C1 = cyc1(adj[P], 1);
    memset(visit, false, sizeof visit);
    C2 = cyc2(adj[P+N], 1);
    if (C1 != -1) for (int i=C1; i<=6*N; i++) cnt1[i] += cnt1[i-C1];
    if (C2 != -1) for (int i=C2; i<=6*N; i++) cnt2[i] += cnt2[i-C2];
    int t1=0, t2=0;
    if (C1 != -1) while (t1 < 2*N) t1 += C1;
    if (C2 != -1) while (t2 < 2*N) t2 += C2;
    for (int i=0; i<Q; i++){
        if (d[i] <= 2*N) answer(cnt1[d[i]] + cnt2[d[i]]);
        else{
            int ans=0;
            if (C1 != -1) ans += cnt1[t1+d[i]%C1];
            if (C2 != -1) ans += cnt2[t2+d[i]%C2];
            answer(ans);
        }
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13432 KB Output is correct
2 Correct 15 ms 13528 KB Output is correct
3 Correct 15 ms 13468 KB Output is correct
4 Correct 14 ms 13304 KB Output is correct
5 Correct 14 ms 13264 KB Output is correct
6 Correct 16 ms 13532 KB Output is correct
7 Correct 14 ms 13268 KB Output is correct
8 Correct 14 ms 13504 KB Output is correct
9 Correct 17 ms 13688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13432 KB Output is correct
2 Correct 15 ms 13528 KB Output is correct
3 Correct 15 ms 13468 KB Output is correct
4 Correct 14 ms 13304 KB Output is correct
5 Correct 14 ms 13264 KB Output is correct
6 Correct 16 ms 13532 KB Output is correct
7 Correct 14 ms 13268 KB Output is correct
8 Correct 14 ms 13504 KB Output is correct
9 Correct 17 ms 13688 KB Output is correct
10 Correct 14 ms 13276 KB Output is correct
11 Correct 28 ms 16732 KB Output is correct
12 Correct 51 ms 19064 KB Output is correct
13 Correct 69 ms 31824 KB Output is correct
14 Correct 156 ms 32216 KB Output is correct
15 Correct 194 ms 32544 KB Output is correct
16 Correct 146 ms 27552 KB Output is correct
17 Correct 138 ms 24172 KB Output is correct
18 Correct 49 ms 17372 KB Output is correct
19 Correct 165 ms 32096 KB Output is correct
20 Correct 201 ms 32572 KB Output is correct
21 Correct 156 ms 25356 KB Output is correct
22 Correct 148 ms 25884 KB Output is correct
23 Correct 167 ms 34032 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13432 KB Output is correct
2 Correct 15 ms 13528 KB Output is correct
3 Correct 15 ms 13468 KB Output is correct
4 Correct 14 ms 13304 KB Output is correct
5 Correct 14 ms 13264 KB Output is correct
6 Correct 16 ms 13532 KB Output is correct
7 Correct 14 ms 13268 KB Output is correct
8 Correct 14 ms 13504 KB Output is correct
9 Correct 17 ms 13688 KB Output is correct
10 Correct 14 ms 13276 KB Output is correct
11 Correct 28 ms 16732 KB Output is correct
12 Correct 51 ms 19064 KB Output is correct
13 Correct 69 ms 31824 KB Output is correct
14 Correct 156 ms 32216 KB Output is correct
15 Correct 194 ms 32544 KB Output is correct
16 Correct 146 ms 27552 KB Output is correct
17 Correct 138 ms 24172 KB Output is correct
18 Correct 49 ms 17372 KB Output is correct
19 Correct 165 ms 32096 KB Output is correct
20 Correct 201 ms 32572 KB Output is correct
21 Correct 156 ms 25356 KB Output is correct
22 Correct 148 ms 25884 KB Output is correct
23 Correct 167 ms 34032 KB Output is correct
24 Correct 15 ms 13264 KB Output is correct
25 Correct 23 ms 16884 KB Output is correct
26 Correct 49 ms 19224 KB Output is correct
27 Correct 81 ms 32092 KB Output is correct
28 Correct 167 ms 32460 KB Output is correct
29 Correct 189 ms 32736 KB Output is correct
30 Correct 165 ms 27768 KB Output is correct
31 Correct 131 ms 24356 KB Output is correct
32 Correct 60 ms 17492 KB Output is correct
33 Correct 150 ms 32360 KB Output is correct
34 Correct 211 ms 32804 KB Output is correct
35 Correct 155 ms 25540 KB Output is correct
36 Correct 162 ms 24388 KB Output is correct
37 Correct 172 ms 34336 KB Output is correct
38 Correct 161 ms 42060 KB Output is correct