oj.uz

Submission #1078916

# Submission time Handle Problem Language Result Execution time Memory
1078916 2024-08-28T08:06:00 Z dwuy Tropical Garden (IOI11_garden) C++14
100 / 100
 1097 ms 32832 KB 
/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5e8;
const int MX = 350005;

int n, m, P;
int L1, L2;
int deg[MX];
int nxt[MX];
int dis1[MX];
int dis2[MX];
vector<int> rG[MX];

void dfs1(int u){
    for(int v: rG[u]) if(dis1[v] > dis1[u] + 1){
        dis1[v] = dis1[u] + 1;
        dfs1(v);
    }
}

void dfs2(int u){
    for(int v: rG[u]) if(dis2[v] > dis2[u] + 1){
        dis2[v] = dis2[u] + 1;
        dfs2(v);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int QR[]){
    n = N;
    m = M;
    ::P = ++P;
    memset(nxt, -1, sizeof nxt);
    for(int i=0; i<m; i++) deg[R[i][0] + 1]++, deg[R[i][1] + 1]++;
    for(int i=0; i<m; i++){
        int u = R[i][0] + 1;
        int v = R[i][1] + 1;
        if(nxt[u] == -1) nxt[u] = deg[v] > 1 && nxt[v] == -1? v + n : v;
        else if(nxt[u + n] == -1) nxt[u + n] = deg[v] > 1 && nxt[v] == -1? v + n : v;
        if(nxt[v] == -1) nxt[v] = deg[u] > 1 && nxt[u] == v + n? u + n : u;
        else if(nxt[v + n] == -1) nxt[v + n] = deg[u] > 1 && nxt[u] == v? u + n : u;
    }
    for(int i=1; i<=n+n; i++) rG[nxt[i]].push_back(i);
    memset(dis1, 0x3f, sizeof dis1);
    memset(dis2, 0x3f, sizeof dis2);
    dis1[P] = dis2[P + n] = 0;
    dfs1(P);
    dfs2(P + n);

    int L1 = INF;
    int L2 = INF;
    for(int u=P, i=1; i<=n+n; i++){
        u = nxt[u];
        if(u == P){
            L1 = i;
            break;
        }
    }
    for(int u=P+n, i=1; i<=n+n; i++){
        u = nxt[u];
        if(u == P + n){
            L2 = i;
            break;
        }
    }
    for(int i=0; i<Q; i++){
        int k = QR[i];
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(k >= dis1[i] && (k - dis1[i])%L1 == 0) ans++;
            else if(k >= dis2[i] && (k - dis2[i])%L2 == 0) ans++;
        }
        answer(ans);
    }
}

/*
6 8 0
1 3
0 2
3 5
0 4
4 3
2 5
4 1
2 3
10
1 8 192 384 3476 9483 23417 332764 342 46  




*/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12880 KB Output is correct
2 Correct 6 ms 12636 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Correct 6 ms 12636 KB Output is correct
6 Correct 6 ms 12752 KB Output is correct
7 Correct 5 ms 12672 KB Output is correct
8 Correct 5 ms 12636 KB Output is correct
9 Correct 9 ms 12868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12880 KB Output is correct
2 Correct 6 ms 12636 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Correct 6 ms 12636 KB Output is correct
6 Correct 6 ms 12752 KB Output is correct
7 Correct 5 ms 12672 KB Output is correct
8 Correct 5 ms 12636 KB Output is correct
9 Correct 9 ms 12868 KB Output is correct
10 Correct 7 ms 12888 KB Output is correct
11 Correct 9 ms 14232 KB Output is correct
12 Correct 16 ms 15268 KB Output is correct
13 Correct 33 ms 27988 KB Output is correct
14 Correct 47 ms 20688 KB Output is correct
15 Correct 51 ms 20948 KB Output is correct
16 Correct 41 ms 19288 KB Output is correct
17 Correct 38 ms 18520 KB Output is correct
18 Correct 19 ms 15196 KB Output is correct
19 Correct 50 ms 20692 KB Output is correct
20 Correct 50 ms 20940 KB Output is correct
21 Correct 42 ms 19036 KB Output is correct
22 Correct 45 ms 18404 KB Output is correct
23 Correct 41 ms 21372 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12880 KB Output is correct
2 Correct 6 ms 12636 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Correct 6 ms 12636 KB Output is correct
6 Correct 6 ms 12752 KB Output is correct
7 Correct 5 ms 12672 KB Output is correct
8 Correct 5 ms 12636 KB Output is correct
9 Correct 9 ms 12868 KB Output is correct
10 Correct 7 ms 12888 KB Output is correct
11 Correct 9 ms 14232 KB Output is correct
12 Correct 16 ms 15268 KB Output is correct
13 Correct 33 ms 27988 KB Output is correct
14 Correct 47 ms 20688 KB Output is correct
15 Correct 51 ms 20948 KB Output is correct
16 Correct 41 ms 19288 KB Output is correct
17 Correct 38 ms 18520 KB Output is correct
18 Correct 19 ms 15196 KB Output is correct
19 Correct 50 ms 20692 KB Output is correct
20 Correct 50 ms 20940 KB Output is correct
21 Correct 42 ms 19036 KB Output is correct
22 Correct 45 ms 18404 KB Output is correct
23 Correct 41 ms 21372 KB Output is correct
24 Correct 6 ms 12632 KB Output is correct
25 Correct 42 ms 14172 KB Output is correct
26 Correct 77 ms 15324 KB Output is correct
27 Correct 703 ms 28108 KB Output is correct
28 Correct 597 ms 20776 KB Output is correct
29 Correct 733 ms 20940 KB Output is correct
30 Correct 403 ms 19360 KB Output is correct
31 Correct 359 ms 18516 KB Output is correct
32 Correct 90 ms 15192 KB Output is correct
33 Correct 632 ms 20684 KB Output is correct
34 Correct 717 ms 20984 KB Output is correct
35 Correct 411 ms 19252 KB Output is correct
36 Correct 631 ms 18512 KB Output is correct
37 Correct 411 ms 21496 KB Output is correct
38 Correct 1097 ms 32832 KB Output is correct