Submission #1105140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105140		anarch_y	Tropical Garden (IOI11_garden)	C++17	0 / 100	3 ms	10832 KiB

garden

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

#include "gardenlib.h"

const int maxn = 300000;
vector<int> adj[maxn];
bool bl[maxn], vis[maxn];
int d[maxn];

void dfs(int s, int p){
    if(vis[s]) return;
    vis[s] = true;
    if(p != -1) d[s] = d[p]+1;
    for(auto u: adj[s]){
        if(u == p or bl[u]) continue;
        dfs(u, s);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    int n, m; n = N, m = M;
    vector<pair<int, int>> vec[n];
    int mn[n] = {};
    for(int i=1; i<=m; i++){
        int a, b; a = R[i-1][0], b = R[i-1][1];
        vec[a].pb({b, i}); vec[b].pb({a, i});
        if(mn[a] == 0) mn[a] = i;
        if(mn[b] == 0) mn[b] = i; 
    } 
    int to[2*n] = {};
    for(int a=0; a<n; a++){
        auto [b, i] = vec[a][0];
        if(mn[b] == i) to[a] = n+b;
        else to[a] = b;
        if(sz(vec[a]) >= 2){
            auto [c, j] = vec[a][1];
            if(mn[c] == j) to[n+a] = n+c;
            else to[n+a] = c; 
        }
        else{
            if(mn[b] == i) to[n+a] = n+b;
            else to[n+a] = b;
        }
    }
    for(int a=0; a<2*n; a++){
        adj[a].pb(to[a]); adj[to[a]].pb(a);
    }
    int p; p = P;
    int q; q = Q;
    int qry[q] = {};
    for(int i=0; i<q; i++) qry[i] = G[i];
    int ans[q] = {};
    {
        int p1 = to[p], p2 = to[to[p]];
        while(p1 != p2){
            p1 = to[p1];
            p2 = to[to[p2]];
        }
        p2 = p;
        while(p1 != p2){
            p1 = to[p1];
            p2 = to[p2];
        }
        fill(bl, bl+2*n, 0);
        fill(vis, vis+2*n, 0);
        vector<int> cyc;
        cyc.pb(p1);
        bl[p1] = 1;
        int ok = 0;
        if(p1 == p) ok = 1;
        int x = to[p1];
        while(x != p1){
            if(x == p) ok = 1;
            cyc.pb(x);
            bl[x] = 1;
            x = to[x];
        }
        int l = sz(cyc);
        fill(d, d+2*n, -1);
        if(ok){
            d[p] = 0;
            dfs(p, -1);
            x = to[p];
            int c = l-1;
            while(x != p){
                d[x] = c;
                dfs(x, -1);
                x = to[x];
                c--;
            }
        }
        else{
            d[p] = 0;
            dfs(p, -1);
        }
        for(int i=0; i<q; i++){
            int k = qry[i];
            for(int a=0; a<n; a++){
                if(d[a] == -1) continue;
                if(ok){
                    if((k-d[a])%l == 0) ans[i]++;
                }
                else{
                    if(k == d[a]) ans[i]++;
                }
            } 
        }
    }    
    p = n+p;
    {
        int p1 = to[p], p2 = to[to[p]];
        while(p1 != p2){
            p1 = to[p1];
            p2 = to[to[p2]];
        }
        p2 = p;
        while(p1 != p2){
            p1 = to[p1];
            p2 = to[p2];
        }
        fill(bl, bl+2*n, 0);
        fill(vis, vis+2*n, 0);
        vector<int> cyc;
        cyc.pb(p1);
        bl[p1] = 1;
        int ok = 0;
        if(p1 == p) ok = 1;
        int x = to[p1];
        while(x != p1){
            if(x == p) ok = 1;
            cyc.pb(x);
            bl[x] = 1;
            x = to[x];
        }
        int l = sz(cyc);
        fill(d, d+2*n, -1);
        if(ok){
            d[p] = 0;
            dfs(p, -1);
            x = to[p];
            int c = l-1;
            while(x != p){
                d[x] = c;
                dfs(x, -1);
                x = to[x];
                c--;
            }
        }
        else{
            d[p] = 0;
            dfs(p, -1);
        }
        for(int i=0; i<q; i++){
            int k = qry[i];
            for(int a=0; a<n; a++){
                if(d[a] == -1) continue;
                if(ok){
                    if((k-d[a])%l == 0) ans[i]++;
                }
                else{
                    if(k == d[a]) ans[i]++;
                }
            } 
        }
    }    
    for(int i=0; i<q; i++){
        answer(ans[i]);
    }
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31