oj.uz

Submission #548588

# Submission time Handle Problem Language Result Execution time Memory
548588 2022-04-13T21:17:25 Z Lobo Tropical Garden (IOI11_garden) C++17
69 / 100
 2498 ms 35184 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 4e5+10;

int n, mark[maxn], p[maxn], ordc[maxn], nx[maxn], disp[maxn], szc[maxn], tin[maxn], tout[maxn], timer;
vector<pair<int,int>> g[maxn];

void dfsc(int v, int ini) {
    p[v] = v;
    disp[v] = 0;
    if(nx[v] == ini) {
        szc[mark[v]] = ordc[v]+1;
        return;
    }
    ordc[nx[v]] = ordc[v]+1;
    dfsc(nx[v],ini);
}

void dfs(int v, int cur) {
    tin[v] = ++timer;

    mark[v] = cur;
    if(mark[nx[v]] == cur) {
        //temos um ciclo
        ordc[nx[v]] = 0;
        dfsc(nx[v],nx[v]);
        tout[v] = timer;
        return;
    }
    else if(mark[nx[v]] == -1){
        dfs(nx[v],cur);
    }

    if(p[v] == -1) {
        disp[v] = disp[nx[v]]+1;
        p[v] = p[nx[v]];
    }

    tout[v] = timer;

}


void count_routes(int32_t N, int32_t M, int32_t P, int32_t R[][2], int32_t Q, int32_t G[]) {
    n = N;
    for(int i = 0; i < M; i++) {
        g[R[i][0]].pb(mp(i,R[i][1]));
        g[R[i][1]].pb(mp(i,R[i][0]));
    }


    for(int i = 0; i < 2*n; i++) {
        nx[i] = i;
    }

    for(int i = 0; i < n; i++) {
        sort(all(g[i]));
    }
    for(int i = 0; i < n; i++) {

        nx[i] = g[i][0].sc;
        if(g[nx[i]][0].sc == i)
            nx[i]+= n;

        if(g[i].size() == 1)
            nx[i+n] = g[i][0].sc;
        else
            nx[i+n] = g[i][1].sc;
        if(g[nx[i+n]][0].sc == i)
            nx[i+n]+= n;
    }

    for(int i = 0; i < 2*n; i++) {
        p[i] = -1;
        mark[i] = -1;
        ordc[i] = -1;
    }

    for(int i = 0; i < 2*n; i++) {
        if(mark[i] == -1) {
            dfs(i,i);
        }
    }

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

            int k = G[j];
            int v = i;
            if(P != p[P]) {
                if(p[v] == p[P] && tin[P] <= tin[v] && tout[v] <= tout[P] && k == disp[v]-disp[P])
                    ans++; 
            }
            else {
                if(mark[p[v]] == mark[P] && k >= disp[v] && (ordc[p[v]]+k-disp[v])%szc[mark[p[v]]] == ordc[P])
                    ans++;

                //vai k pra frente de 
            }

            P+= n;
            if(P != p[P]) {
                if(p[v] == p[P] && tin[P] <= tin[v] && tout[v] <= tout[P] && k == disp[v]-disp[P])
                    ans++; 
            }
            else {
                if(mark[p[v]] == mark[P] && k >= disp[v] && (ordc[p[v]]+k-disp[v])%szc[mark[p[v]]] == ordc[P])
                    ans++;

                //vai k pra frente de 
            }
            P-= n;


        }
        answer(ans);
        // cout << ans << endl;
    }
}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
//     // freopen("out.out", "w", stdout);
    
//     int32_t N, M, P;
//     cin >> N >> M >> P;
//     int32_t R[M][2];
//     for(int i = 0; i < M; i++) {
//         cin >> R[i][0] >> R[i][1];
//     }
//     int32_t Q; cin >> Q;
//     int32_t G[Q];
//     for(int i = 0; i < Q; i++) {
//         cin >> G[i];
//     }

//     count_routes(N,M,P,R,Q,G);

// }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 7 ms 10324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 7 ms 10324 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 15 ms 13780 KB Output is correct
12 Correct 24 ms 17236 KB Output is correct
13 Correct 36 ms 28984 KB Output is correct
14 Correct 69 ms 33100 KB Output is correct
15 Correct 76 ms 33680 KB Output is correct
16 Correct 66 ms 28436 KB Output is correct
17 Correct 64 ms 26536 KB Output is correct
18 Correct 25 ms 17068 KB Output is correct
19 Correct 75 ms 32980 KB Output is correct
20 Correct 80 ms 33552 KB Output is correct
21 Correct 66 ms 28024 KB Output is correct
22 Correct 76 ms 26176 KB Output is correct
23 Correct 77 ms 35184 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 7 ms 10324 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 15 ms 13780 KB Output is correct
12 Correct 24 ms 17236 KB Output is correct
13 Correct 36 ms 28984 KB Output is correct
14 Correct 69 ms 33100 KB Output is correct
15 Correct 76 ms 33680 KB Output is correct
16 Correct 66 ms 28436 KB Output is correct
17 Correct 64 ms 26536 KB Output is correct
18 Correct 25 ms 17068 KB Output is correct
19 Correct 75 ms 32980 KB Output is correct
20 Correct 80 ms 33552 KB Output is correct
21 Correct 66 ms 28024 KB Output is correct
22 Correct 76 ms 26176 KB Output is correct
23 Correct 77 ms 35184 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 126 ms 13772 KB Output is correct
26 Correct 167 ms 17280 KB Output is correct
27 Correct 2228 ms 29092 KB Output is correct
28 Correct 1077 ms 33232 KB Output is correct
29 Correct 2498 ms 33828 KB Output is correct
30 Correct 1391 ms 28392 KB Output is correct
31 Correct 1463 ms 26668 KB Output is correct
32 Incorrect 258 ms 17072 KB Output isn't correct
33 Halted 0 ms 0 KB -