Submission #1113929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113929		lucascgar	Tropical Garden (IOI11_garden)	C++17	49 / 100	46 ms	15688 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

/*
só interessam as duas arestas mais valiosas de um cara
ou vc ta em um ciclo ou vc escoa um ciclo

*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 150000+10, MAXQ = 2e3+10, BIG = 1e9+1;

vector<pii> e[MAXN];

int ds[MAXN][2];  // distância até p
bool st[MAXN][2];  // o estado que pega p


bool dfs(int x, int l, int P){
    bool cr = 0;
    if (e[x].size() > 1 && l == e[x][0].second) cr=1;

    if (ds[x][cr] != BIG) return cr;
    ds[x][cr] = -1;

    auto i = e[x][cr].first;
    if (i == P){
        ds[x][cr] = 1, st[x][cr] = (e[i].size()>1 && e[x][cr].second==e[i][0].second);
        return cr;
    }

    bool is = dfs(i, e[x][cr].second, P);

    if (ds[i][is] != -1){
        ds[x][cr] = ds[i][is]+1;
        st[x][cr] = st[i][is];
    }

    return cr;

}

void count_routes(int n, int m, int P, int R[][2], int q, int G[]){

    for (int i=0;i<n;i++){
        e[i].clear();
        ds[i][0] = ds[i][1] = BIG;
    }

    for (int i=0;i<m;i++){
        int a = R[i][0], b = R[i][1];
        if (e[a].size()<2) e[a].emplace_back(b, i);
        if (e[b].size()<2) e[b].emplace_back(a, i);
    }

    for (int i=0;i<n;i++){
        if (ds[i][0] == BIG) dfs(i, -1, P);
    }

    if(!e[P].empty()) dfs(P, e[P][0].second, P);
    // for (int i=0;i<n;i++) cerr << ds[i][0] << ' ' << ds[i][1] << '\n';

    for (int _=0;_<q;_++){
        int sk = G[_], cr = 0;

        for (int i=0;i<n;i++) if (ds[i][0] != -1 && ds[i][0]<=sk){
            int k = sk;
            long long d = ds[i][0];
            if (d==k){
                cr++;
                // cerr << i << " can\n";
                continue;
            }
            k-=d;

            vector<int> vi(2, -1);
            long long ex=0, cy=0;
    
            bool cst = st[i][0];

            vi[cst]=0;
            while (1){
                ex+=ds[P][cst];
                if (ex==k) break;
                cst = st[P][cst];
                if (vi[cst] != -1){
                    cy = ex-vi[cst];
                    break;
                }
                vi[cst] = ex;
            }
            if(ex>k) continue;

            if (ex==k || (st[P][cst] == cst && cy!=0)){  // ciclo de uma parte ou interrompido
                if (ex==k || (k-ex)%cy == 0){
                    cr++;
                    // cerr << i << " can\n";
                }
            }else if(cy!=0){  // ciclo de duas partes
                long long psm = ds[P][cst];
                int v = (k-ex)%cy;
                if (v == 0 || v==psm){
                    cr++; // ciclo todo ou finaliza no pequeno
                    // cerr << i << " can\n";
                }
                // if (i==4) cerr << k << ' ' << cst << ' ' << ex << ' ' << cy << ' ' << psm << '\n';
            }
            

        }

        answer(cr);
        // cout << cr << '\n';

    }

}
// int G[MAXN], R[MAXN][2];
// signed main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int n, m, p, q;
//     cin >> n >> m >> p >> q;

//     for (int i=0;i<m;i++){
//         cin >> R[i][0] >> R[i][1];
//     }

//     for (int i=0;i<q;i++) cin >> G[i];

//     count_routes(n, m, p, R, q, G);

//     return 0;
// }

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31