oj.uz

Submission #548554

# Submission time Handle Problem Language Result Execution time Memory
548554 2022-04-13T19:41:31 Z Lobo Tropical Garden (IOI11_garden) C++17
69 / 100
 2541 ms 31180 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];
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) {

    mark[v] = cur;
    if(mark[nx[v]] == cur) {
        //temos um ciclo
        ordc[nx[v]] = 0;
        dfsc(nx[v],nx[v]);
        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]];
    }
}


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++) {
        if(g[i].size() == 0) continue;

        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;
        // cout << i << " " << nx[i] << " " << nx[i+n] << endl;
    }

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

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

    // for(int i = 0; i < 2*n; i++) {
    //     cout << i << " " << p[i] << " " << disp[i] << endl;
    // }

    for(int j = 0; j < Q; j++) {
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(nx[i] == i) continue;

            int k = G[j];
            int v = i;
            if(P != p[P]) {
                if(p[v] == p[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] && 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[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 6 ms 9892 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9748 KB Output is correct
5 Correct 5 ms 9704 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9836 KB Output is correct
9 Correct 7 ms 10356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9892 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9748 KB Output is correct
5 Correct 5 ms 9704 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9836 KB Output is correct
9 Correct 7 ms 10356 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 17 ms 13268 KB Output is correct
12 Correct 25 ms 16636 KB Output is correct
13 Correct 36 ms 27284 KB Output is correct
14 Correct 76 ms 29928 KB Output is correct
15 Correct 77 ms 30436 KB Output is correct
16 Correct 66 ms 26308 KB Output is correct
17 Correct 66 ms 25000 KB Output is correct
18 Correct 28 ms 16344 KB Output is correct
19 Correct 71 ms 29524 KB Output is correct
20 Correct 89 ms 30148 KB Output is correct
21 Correct 69 ms 25940 KB Output is correct
22 Correct 68 ms 24588 KB Output is correct
23 Correct 73 ms 31180 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9892 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9748 KB Output is correct
5 Correct 5 ms 9704 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9836 KB Output is correct
9 Correct 7 ms 10356 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 17 ms 13268 KB Output is correct
12 Correct 25 ms 16636 KB Output is correct
13 Correct 36 ms 27284 KB Output is correct
14 Correct 76 ms 29928 KB Output is correct
15 Correct 77 ms 30436 KB Output is correct
16 Correct 66 ms 26308 KB Output is correct
17 Correct 66 ms 25000 KB Output is correct
18 Correct 28 ms 16344 KB Output is correct
19 Correct 71 ms 29524 KB Output is correct
20 Correct 89 ms 30148 KB Output is correct
21 Correct 69 ms 25940 KB Output is correct
22 Correct 68 ms 24588 KB Output is correct
23 Correct 73 ms 31180 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 131 ms 13332 KB Output is correct
26 Correct 184 ms 16596 KB Output is correct
27 Correct 2226 ms 27308 KB Output is correct
28 Correct 1100 ms 29744 KB Output is correct
29 Correct 2541 ms 30188 KB Output is correct
30 Correct 1396 ms 26300 KB Output is correct
31 Correct 1451 ms 25144 KB Output is correct
32 Incorrect 275 ms 16588 KB Output isn't correct
33 Halted 0 ms 0 KB -