oj.uz

Submission #1113919

# Submission time Handle Problem Language Result Execution time Memory
1113919 2024-11-17T19:47:00 Z lucascgar Tropical Garden (IOI11_garden) C++17
49 / 100
 21 ms 14516 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];
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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 2 ms 6480 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 2 ms 6480 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 6 ms 7504 KB Output is correct
12 Correct 11 ms 8016 KB Output is correct
13 Incorrect 21 ms 14516 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6480 KB Output is correct
8 Correct 3 ms 6480 KB Output is correct
9 Correct 2 ms 6480 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 6 ms 7504 KB Output is correct
12 Correct 11 ms 8016 KB Output is correct
13 Incorrect 21 ms 14516 KB Output isn't correct
14 Halted 0 ms 0 KB -