oj.uz

Submission #1108102

# Submission time Handle Problem Language Result Execution time Memory
1108102 2024-11-02T18:25:08 Z laight Tropical Garden (IOI11_garden) C++17
100 / 100
 1507 ms 41204 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pi pair<int, int>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define umi unordered_map<int, int>
#define umll unordered_map<ll, ll>
#define umllv unordered_map<ll, vector<ll>>
 
#define getchar() (*_pinp?*_pinp++:(_inp[fread(_pinp=_inp, 1, 4096, stdin)]='\0', *_pinp++))
char _inp[4097], *_pinp=_inp;
#define scan(x) do{while((x=getchar())<'-'); _ssign=x=='-'; if(_ssign) while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0'); x=_ssign?-x:x;}while(0)
char _; bool _ssign;
 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
 
using namespace std; using namespace __gnu_pbds;
 
const int MM = 1e5+5e4+5;
const ll inf = 2e15+1;
const int lg = 17; // 17 for 1e5, 31 for 1e9
 
int n, m, p, a, b, dis[2*MM], dis2[2*MM], lv, cycl, cl1, cl2, q, inp; bool cvis[2*MM], vis[2*MM], vis2[2*MM], hcy, cy1, cy2;
vector<int> g(2005), ans(2005), to(2*MM), rev[2*MM], graph[MM];
 
void g_f(int c, int d){
    if (vis[c]) return;
    vis[c] = 1; dis[c] = d;
    for (int i : rev[c]){
        g_f(i, d+1);
    }
}
void g_f2(int c, int d){
    if (vis2[c]) return;
    vis2[c] = 1; dis2[c] = d;
    for (int i : rev[c]){
        g_f2(i, d+1);
    }
}
void cyc_f(int c, int d, int pe){
    if (cvis[c]){
        if (c == pe) {hcy = 1; cycl = d;}
        return;
    }
    cvis[c] = 1; cyc_f(to[c], d+1, pe);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    // cin.tie(0); cin.sync_with_stdio(0);
    // freopen("changyue_tst.txt", "r", stdin);
    n = N; m = M; p = P;
    for (int i=0; i<m; ++i){
        graph[R[i][0]].pb(R[i][1]); graph[R[i][1]].pb(R[i][0]);
    }
    q = Q; for (int i=0; i<q; i++) {g[i] = G[i];}
    for (int i=0; i<n; ++i){
        int oth = graph[i][0];
        if (i == graph[oth][0]){
            to[i] = n+oth;
        }
        else {to[i] = oth;}
        if (graph[i].size() >= 2){
            int oth2 = graph[i][1];
            if (i == graph[oth2][0]){
                to[n+i] = n+oth2;
            }
            else {to[n+i] = oth2;}
        }
        else{
            if (i == graph[oth][0]){
                to[n+i] = n+oth;
            }
            else {to[n+i] = oth;}
        }
    }
    for (int i=0; i<2*n; i++){
        rev[to[i]].pb(i);
    }
    hcy = 0; cycl = 0;
    cyc_f(p, 0, p);
    cl1 = cycl; cy1 = hcy;
    memset(cvis, 0, sizeof(cvis));
    hcy = 0; cycl = 0;
    cyc_f(n+p, 0, n+p);
    cl2 = cycl; cy2 = hcy;
    g_f(p, 0); g_f2(n+p, 0);
    for (int i=0; i<q; ++i){
        int tv=g[i], ca=0;
        for (int j=0; j<n; ++j){
            int addon=0;
            if (cy1 && vis[j]){
                if (tv >= dis[j] && (tv%cl1 == dis[j]%cl1)){
                    addon = 1;
                }
            }
            else if (vis[j]){
                if (tv == dis[j]) addon = 1;
            }
            if (cy2 && vis2[j]){
                if (tv >= dis2[j] && (tv%cl2 == dis2[j]%cl2)){
                    addon = 1;
                }
            }
            else if (vis2[j]){
                if (tv == dis2[j]) addon = 1;
            }
            ca += addon;
        }
        answer(ca);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16208 KB Output is correct
2 Correct 4 ms 16208 KB Output is correct
3 Correct 4 ms 16208 KB Output is correct
4 Correct 4 ms 15952 KB Output is correct
5 Correct 3 ms 15952 KB Output is correct
6 Correct 5 ms 16208 KB Output is correct
7 Correct 5 ms 15952 KB Output is correct
8 Correct 4 ms 16208 KB Output is correct
9 Correct 5 ms 16208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16208 KB Output is correct
2 Correct 4 ms 16208 KB Output is correct
3 Correct 4 ms 16208 KB Output is correct
4 Correct 4 ms 15952 KB Output is correct
5 Correct 3 ms 15952 KB Output is correct
6 Correct 5 ms 16208 KB Output is correct
7 Correct 5 ms 15952 KB Output is correct
8 Correct 4 ms 16208 KB Output is correct
9 Correct 5 ms 16208 KB Output is correct
10 Correct 4 ms 15952 KB Output is correct
11 Correct 10 ms 17744 KB Output is correct
12 Correct 18 ms 19272 KB Output is correct
13 Correct 40 ms 33120 KB Output is correct
14 Correct 53 ms 28744 KB Output is correct
15 Correct 75 ms 28960 KB Output is correct
16 Correct 45 ms 26400 KB Output is correct
17 Correct 48 ms 25232 KB Output is correct
18 Correct 24 ms 19324 KB Output is correct
19 Correct 56 ms 28488 KB Output is correct
20 Correct 69 ms 28824 KB Output is correct
21 Correct 49 ms 26184 KB Output is correct
22 Correct 43 ms 25404 KB Output is correct
23 Correct 50 ms 29768 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16208 KB Output is correct
2 Correct 4 ms 16208 KB Output is correct
3 Correct 4 ms 16208 KB Output is correct
4 Correct 4 ms 15952 KB Output is correct
5 Correct 3 ms 15952 KB Output is correct
6 Correct 5 ms 16208 KB Output is correct
7 Correct 5 ms 15952 KB Output is correct
8 Correct 4 ms 16208 KB Output is correct
9 Correct 5 ms 16208 KB Output is correct
10 Correct 4 ms 15952 KB Output is correct
11 Correct 10 ms 17744 KB Output is correct
12 Correct 18 ms 19272 KB Output is correct
13 Correct 40 ms 33120 KB Output is correct
14 Correct 53 ms 28744 KB Output is correct
15 Correct 75 ms 28960 KB Output is correct
16 Correct 45 ms 26400 KB Output is correct
17 Correct 48 ms 25232 KB Output is correct
18 Correct 24 ms 19324 KB Output is correct
19 Correct 56 ms 28488 KB Output is correct
20 Correct 69 ms 28824 KB Output is correct
21 Correct 49 ms 26184 KB Output is correct
22 Correct 43 ms 25404 KB Output is correct
23 Correct 50 ms 29768 KB Output is correct
24 Correct 4 ms 15952 KB Output is correct
25 Correct 95 ms 18136 KB Output is correct
26 Correct 127 ms 19272 KB Output is correct
27 Correct 1367 ms 33096 KB Output is correct
28 Correct 781 ms 28744 KB Output is correct
29 Correct 1146 ms 29096 KB Output is correct
30 Correct 778 ms 26428 KB Output is correct
31 Correct 693 ms 25448 KB Output is correct
32 Correct 136 ms 19280 KB Output is correct
33 Correct 820 ms 28840 KB Output is correct
34 Correct 1152 ms 29000 KB Output is correct
35 Correct 778 ms 26248 KB Output is correct
36 Correct 809 ms 25456 KB Output is correct
37 Correct 683 ms 29900 KB Output is correct
38 Correct 1507 ms 41204 KB Output is correct