Submission #1113919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113919		lucascgar	Tropical Garden (IOI11_garden)	C++17	49 / 100	21 ms	14516 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];
bool inl[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();
        inl[i]=0, 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 k = G[_], cr = 0;

        for (int i=0;i<n;i++) if (ds[i][0] != -1){

            long long d = ds[i][0], fc = ds[P][st[i][0]], sc = ds[P][st[P][st[i][0]]];
            if (d>k) continue;
    
            if (d==k){
                cr++;
            }else if(fc!=-1 && d+fc<=k){

                if ((d+fc-k)%sc == 0){
                    cr++;
                }
            }


        }

        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