oj.uz

Submission #954987

# Submission time Handle Problem Language Result Execution time Memory
954987 2024-03-29T04:59:15 Z GrindMachine Tropical Garden (IOI11_garden) C++17
100 / 100
 1598 ms 38852 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "garden.h"
#include "gardenlib.h"

vector<int> adj1[N], adj2[N];

void count_routes(int n, int m, int p, int R[][2], int q, int a[])
{
    rep(i,m){
        int u = R[i][0], v = R[i][1];
        adj1[u].pb(v), adj1[v].pb(u);
    }

    vector<int> nxt(n*2,-1);

    rep(u,n){
        auto edges = adj1[u];
        if(sz(edges) >= 2){
            {
                int v = edges[1];
                if(u == adj1[v][0]){
                    nxt[u*2] = v*2;
                }
                else{
                    nxt[u*2] = v*2+1;
                }
            }

            {
                int v = edges[0];
                if(u == adj1[v][0]){
                    nxt[u*2+1] = v*2;
                }
                else{
                    nxt[u*2+1] = v*2+1;
                }
            }
        }
        else{
            int v = edges[0];
            if(u == adj1[v][0]){
                nxt[u*2] = v*2;
            }
            else{
                nxt[u*2] = v*2+1;
            }
        }
    }

    vector<int> indeg(2*n);
    rep(i,2*n){
        if(nxt[i] != -1){
            indeg[nxt[i]]++;
        }
    }

    queue<int> que;
    rep(i,2*n){
        if(!indeg[i]){
            que.push(i);
        }
    }    

    while(!que.empty()){
        int u = que.front();
        que.pop();

        if(nxt[u] != -1){
            indeg[nxt[u]]--;
            if(!indeg[nxt[u]]){
                que.push(nxt[u]);
            }
        }
    }

    vector<int> cyc_siz(2);
    for(int s = p*2; s <= p*2+1; ++s){
        if(!indeg[s]) conts;
        int u = nxt[s];
        cyc_siz[s&1] = 1;
        while(u != s){
            cyc_siz[s&1]++;
            u = nxt[u];
        }
    }

    rep(u,2*n){
        int v = nxt[u];
        if(v == -1) conts;
        adj2[v].pb(u);
    }

    int dis[2*n][2];
    memset(dis,0x3f,sizeof dis);

    rep(x,2){
        que.push(p*2+x);
        dis[p*2+x][x] = 0;

        while(!que.empty()){
            int u = que.front();
            que.pop();

            trav(v,adj2[u]){
                if(dis[u][x]+1 >= dis[v][x]) conts;
                que.push(v);
                dis[v][x] = dis[u][x]+1;
            }
        }
    }

    vector<int> node_id(n);
    rep(i,n){
        node_id[i] = 2*i+1;
        if(sz(adj1[i]) == 1){
            node_id[i]--;
        }
    }

    int modk[q][2];
    memset(modk,-1,sizeof modk);

    rep(i,q){
        int k = a[i];
        rep(j,2){
            if(cyc_siz[j]){
                modk[i][j] = k%cyc_siz[j];
            }
        }
    }

    int mod_dis[2*n][2];
    memset(mod_dis,0x3f,sizeof mod_dis);

    rep(i,2*n){
        rep(j,2){
            if(cyc_siz[j]){
                mod_dis[i][j] = dis[i][j]%cyc_siz[j];
            }
        }
    }

    rep(id,q){
        int k = a[id];
        int ans = 0;

        rep(i,n){
            int u = node_id[i];
            rep(x,2){
                ans += ((dis[u][x] <= k and mod_dis[u][x] == modk[id][x]) or (dis[u][x] == k));
            }
        }

        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 15024 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 5 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 11 ms 17756 KB Output is correct
12 Correct 23 ms 19292 KB Output is correct
13 Correct 36 ms 29268 KB Output is correct
14 Correct 72 ms 32604 KB Output is correct
15 Correct 80 ms 32948 KB Output is correct
16 Correct 67 ms 27992 KB Output is correct
17 Correct 55 ms 26492 KB Output is correct
18 Correct 22 ms 19288 KB Output is correct
19 Correct 73 ms 32520 KB Output is correct
20 Correct 81 ms 32848 KB Output is correct
21 Correct 59 ms 28108 KB Output is correct
22 Correct 59 ms 26472 KB Output is correct
23 Correct 84 ms 34288 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 15024 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 5 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 11 ms 17756 KB Output is correct
12 Correct 23 ms 19292 KB Output is correct
13 Correct 36 ms 29268 KB Output is correct
14 Correct 72 ms 32604 KB Output is correct
15 Correct 80 ms 32948 KB Output is correct
16 Correct 67 ms 27992 KB Output is correct
17 Correct 55 ms 26492 KB Output is correct
18 Correct 22 ms 19288 KB Output is correct
19 Correct 73 ms 32520 KB Output is correct
20 Correct 81 ms 32848 KB Output is correct
21 Correct 59 ms 28108 KB Output is correct
22 Correct 59 ms 26472 KB Output is correct
23 Correct 84 ms 34288 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 89 ms 17776 KB Output is correct
26 Correct 132 ms 19544 KB Output is correct
27 Correct 392 ms 29368 KB Output is correct
28 Correct 868 ms 32852 KB Output is correct
29 Correct 571 ms 32912 KB Output is correct
30 Correct 339 ms 28276 KB Output is correct
31 Correct 321 ms 26452 KB Output is correct
32 Correct 149 ms 19548 KB Output is correct
33 Correct 874 ms 32724 KB Output is correct
34 Correct 498 ms 32768 KB Output is correct
35 Correct 299 ms 28244 KB Output is correct
36 Correct 801 ms 26452 KB Output is correct
37 Correct 724 ms 34116 KB Output is correct
38 Correct 1598 ms 38852 KB Output is correct