oj.uz

Submission #548584

# Submission time Handle Problem Language Result Execution time Memory
548584 2022-04-13T21:01:50 Z Lobo Tropical Garden (IOI11_garden) C++17
69 / 100
 2635 ms 33108 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], 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]);
        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++) {

        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] && k == tin[P]-tin[v] && 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 == tin[P]-tin[v] && 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 6 ms 9812 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 9704 KB Output is correct
5 Correct 6 ms 9704 KB Output is correct
6 Correct 6 ms 9984 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9856 KB Output is correct
9 Correct 7 ms 10352 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 7 ms 9836 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 9704 KB Output is correct
5 Correct 6 ms 9704 KB Output is correct
6 Correct 6 ms 9984 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9856 KB Output is correct
9 Correct 7 ms 10352 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 14 ms 13524 KB Output is correct
12 Correct 25 ms 16708 KB Output is correct
13 Correct 42 ms 27780 KB Output is correct
14 Correct 78 ms 31212 KB Output is correct
15 Correct 90 ms 31716 KB Output is correct
16 Correct 71 ms 27208 KB Output is correct
17 Correct 69 ms 25676 KB Output is correct
18 Correct 29 ms 16596 KB Output is correct
19 Correct 77 ms 31232 KB Output is correct
20 Correct 88 ms 31680 KB Output is correct
21 Correct 67 ms 26848 KB Output is correct
22 Correct 77 ms 25340 KB Output is correct
23 Correct 110 ms 33108 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 7 ms 9836 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 9704 KB Output is correct
5 Correct 6 ms 9704 KB Output is correct
6 Correct 6 ms 9984 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9856 KB Output is correct
9 Correct 7 ms 10352 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 14 ms 13524 KB Output is correct
12 Correct 25 ms 16708 KB Output is correct
13 Correct 42 ms 27780 KB Output is correct
14 Correct 78 ms 31212 KB Output is correct
15 Correct 90 ms 31716 KB Output is correct
16 Correct 71 ms 27208 KB Output is correct
17 Correct 69 ms 25676 KB Output is correct
18 Correct 29 ms 16596 KB Output is correct
19 Correct 77 ms 31232 KB Output is correct
20 Correct 88 ms 31680 KB Output is correct
21 Correct 67 ms 26848 KB Output is correct
22 Correct 77 ms 25340 KB Output is correct
23 Correct 110 ms 33108 KB Output is correct
24 Correct 6 ms 9812 KB Output is correct
25 Correct 113 ms 13544 KB Output is correct
26 Correct 153 ms 16812 KB Output is correct
27 Correct 2346 ms 28016 KB Output is correct
28 Correct 1052 ms 31388 KB Output is correct
29 Correct 2635 ms 31816 KB Output is correct
30 Correct 1403 ms 27216 KB Output is correct
31 Correct 1517 ms 25704 KB Output is correct
32 Incorrect 265 ms 16616 KB Output isn't correct
33 Halted 0 ms 0 KB -