Submission #954993

# Submission time Handle Problem Language Result Execution time Memory
954993 2024-03-29T05:48:24 Z GrindMachine Tropical Garden (IOI11_garden) C++17
0 / 100
3 ms 14940 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];
            }
        }
    }

    vector<pii> queries(q);
    rep(i,q) queries[i] = {a[i],i};
    sort(all(queries));

    vector<int> ans(q);

    rep(x,2){
        vector<pii> sorted_dis;
        rep(i,n){
            int u = node_id[i];
            sorted_dis.pb({dis[u][x],mod_dis[u][x]});
        }

        sort(all(sorted_dis));

        map<int,int> mp1,mp2;
        for(auto [d,md] : sorted_dis){
            mp1[d]++;
        }

        int ptr = 0;

        rep(i,q){
            auto [k,id] = queries[i];
            while(ptr < sz(sorted_dis) and sorted_dis[ptr].ff < k){
                mp2[sorted_dis[ptr++].ss]++;
            }

            ans[id] += mp1[k];
            rep(x,2){
                ans[id] += mp2[modk[id][x]];
            }
        }
    }

    rep(i,q){
        answer(ans[i]);
    }
}
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -