oj.uz

Submission #1113929

# Submission time Handle Problem Language Result Execution time Memory
1113929 2024-11-17T20:40:10 Z lucascgar Tropical Garden (IOI11_garden) C++17
49 / 100
 46 ms 15688 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 2 ms 6480 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6588 KB Output is correct
8 Correct 2 ms 6480 KB Output is correct
9 Correct 3 ms 6592 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 2 ms 6480 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6588 KB Output is correct
8 Correct 2 ms 6480 KB Output is correct
9 Correct 3 ms 6592 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 6 ms 7504 KB Output is correct
12 Correct 14 ms 8528 KB Output is correct
13 Correct 26 ms 15688 KB Output is correct
14 Correct 41 ms 12472 KB Output is correct
15 Correct 46 ms 12548 KB Output is correct
16 Correct 37 ms 11132 KB Output is correct
17 Correct 30 ms 10596 KB Output is correct
18 Incorrect 12 ms 8272 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 2 ms 6480 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6588 KB Output is correct
8 Correct 2 ms 6480 KB Output is correct
9 Correct 3 ms 6592 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 6 ms 7504 KB Output is correct
12 Correct 14 ms 8528 KB Output is correct
13 Correct 26 ms 15688 KB Output is correct
14 Correct 41 ms 12472 KB Output is correct
15 Correct 46 ms 12548 KB Output is correct
16 Correct 37 ms 11132 KB Output is correct
17 Correct 30 ms 10596 KB Output is correct
18 Incorrect 12 ms 8272 KB Output isn't correct
19 Halted 0 ms 0 KB -