Submission #548584

#	Time	Username	Problem	Language	Result	Execution time	Memory
548584		Lobo	Tropical Garden (IOI11_garden)	C++17	69 / 100	2635 ms	33108 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31