제출 #1113953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113953		lucascgar	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	801 ms	20296 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);
    }

    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;
            bool cst = st[i][0];
            if (ds[P][cst] == -1) continue;

            long long fcy = ds[P][cst];
            k -= fcy;
            if (k<=0){
                cr+=(k==0);
                continue;
            }
            bool nst = st[P][cst];

            if (nst == cst){
                cr += (k%fcy == 0);
                continue;
            }

            long long scy = ds[P][nst];
            bool tst = st[P][nst];
            k -= scy;
            if (k<=0){
                cr += (k==0);
                continue;
            }

            if (tst == nst){  // 1->2->2, ciclo simples
                cr += (k%scy == 0);
                continue;                
            }else{  // 1->2->1

                // small = fcy, big = scy
                long long rst = k%(fcy+scy);
                if (rst==0 || rst==fcy) cr++;

                continue;

            }
        }

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

    }

}

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