oj.uz

Submission #548512

# Submission time Handle Problem Language Result Execution time Memory
548512 2022-04-13T16:49:16 Z Lobo Tropical Garden (IOI11_garden) C++17
69 / 100
 2687 ms 30500 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 < 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;
        // 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(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++) {
            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[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);
    }
}

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

//     freopen("in.in", "r", stdin);
//     // freopen("out.out", "w", stdout);
    
//     int N, M, P;
//     cin >> N >> M >> P;
//     int R[M][2];
//     for(int i = 0; i < M; i++) {
//         cin >> R[i][0] >> R[i][1];
//     }
//     int Q; cin >> Q;
//     int 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 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9696 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9972 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 8 ms 10416 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 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9696 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9972 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 8 ms 10416 KB Output is correct
10 Correct 5 ms 9708 KB Output is correct
11 Correct 14 ms 13368 KB Output is correct
12 Correct 26 ms 16468 KB Output is correct
13 Correct 42 ms 26684 KB Output is correct
14 Correct 88 ms 29132 KB Output is correct
15 Correct 93 ms 29560 KB Output is correct
16 Correct 76 ms 25548 KB Output is correct
17 Correct 95 ms 24224 KB Output is correct
18 Correct 27 ms 15884 KB Output is correct
19 Correct 79 ms 28856 KB Output is correct
20 Correct 86 ms 29340 KB Output is correct
21 Correct 73 ms 25088 KB Output is correct
22 Correct 79 ms 23876 KB Output is correct
23 Correct 82 ms 30500 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 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9696 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9972 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 8 ms 10416 KB Output is correct
10 Correct 5 ms 9708 KB Output is correct
11 Correct 14 ms 13368 KB Output is correct
12 Correct 26 ms 16468 KB Output is correct
13 Correct 42 ms 26684 KB Output is correct
14 Correct 88 ms 29132 KB Output is correct
15 Correct 93 ms 29560 KB Output is correct
16 Correct 76 ms 25548 KB Output is correct
17 Correct 95 ms 24224 KB Output is correct
18 Correct 27 ms 15884 KB Output is correct
19 Correct 79 ms 28856 KB Output is correct
20 Correct 86 ms 29340 KB Output is correct
21 Correct 73 ms 25088 KB Output is correct
22 Correct 79 ms 23876 KB Output is correct
23 Correct 82 ms 30500 KB Output is correct
24 Correct 7 ms 9684 KB Output is correct
25 Correct 123 ms 13072 KB Output is correct
26 Correct 170 ms 16264 KB Output is correct
27 Correct 2322 ms 26420 KB Output is correct
28 Correct 1113 ms 28888 KB Output is correct
29 Correct 2687 ms 29416 KB Output is correct
30 Correct 1474 ms 25548 KB Output is correct
31 Correct 1541 ms 24256 KB Output is correct
32 Incorrect 279 ms 16016 KB Output isn't correct
33 Halted 0 ms 0 KB -