oj.uz

Submission #548556

# Submission time Handle Problem Language Result Execution time Memory
548556 2022-04-13T19:45:59 Z Lobo Tropical Garden (IOI11_garden) C++17
69 / 100
 2601 ms 30448 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 || nx[P] == P) 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 9812 KB Output is correct
2 Correct 5 ms 9896 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 10024 KB Output is correct
7 Correct 5 ms 9696 KB Output is correct
8 Correct 5 ms 9784 KB Output is correct
9 Correct 9 ms 10336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 5 ms 9896 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 10024 KB Output is correct
7 Correct 5 ms 9696 KB Output is correct
8 Correct 5 ms 9784 KB Output is correct
9 Correct 9 ms 10336 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 14 ms 13060 KB Output is correct
12 Correct 28 ms 16084 KB Output is correct
13 Correct 42 ms 26420 KB Output is correct
14 Correct 90 ms 28976 KB Output is correct
15 Correct 79 ms 29332 KB Output is correct
16 Correct 70 ms 25460 KB Output is correct
17 Correct 65 ms 24144 KB Output is correct
18 Correct 26 ms 15844 KB Output is correct
19 Correct 85 ms 28864 KB Output is correct
20 Correct 90 ms 29452 KB Output is correct
21 Correct 66 ms 25036 KB Output is correct
22 Correct 70 ms 23756 KB Output is correct
23 Correct 83 ms 30448 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 5 ms 9896 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 10024 KB Output is correct
7 Correct 5 ms 9696 KB Output is correct
8 Correct 5 ms 9784 KB Output is correct
9 Correct 9 ms 10336 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 14 ms 13060 KB Output is correct
12 Correct 28 ms 16084 KB Output is correct
13 Correct 42 ms 26420 KB Output is correct
14 Correct 90 ms 28976 KB Output is correct
15 Correct 79 ms 29332 KB Output is correct
16 Correct 70 ms 25460 KB Output is correct
17 Correct 65 ms 24144 KB Output is correct
18 Correct 26 ms 15844 KB Output is correct
19 Correct 85 ms 28864 KB Output is correct
20 Correct 90 ms 29452 KB Output is correct
21 Correct 66 ms 25036 KB Output is correct
22 Correct 70 ms 23756 KB Output is correct
23 Correct 83 ms 30448 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 165 ms 13040 KB Output is correct
26 Correct 208 ms 16116 KB Output is correct
27 Correct 2323 ms 26420 KB Output is correct
28 Correct 1203 ms 28884 KB Output is correct
29 Correct 2601 ms 29452 KB Output is correct
30 Correct 1506 ms 25524 KB Output is correct
31 Correct 1555 ms 24292 KB Output is correct
32 Incorrect 316 ms 15884 KB Output isn't correct
33 Halted 0 ms 0 KB -