Submission #108338

#	Time	Username	Problem	Language	Result	Execution time	Memory
108338		PeppaPig	Tropical Garden (IOI11_garden)	C++14	0 / 100	17 ms	16120 KiB

garden

#include "gardenlib.h"
#include "garden.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5+5;

int deg[N<<1], d[N<<1];
vector<pii> pre[N];
vector<int> g[N<<1];

void count_routes(int n, int m, int p, int r[][2], int q, int _g[]) {
    fill_n(d, N<<1, 1e9+1);
    for(int i = 0; i < m; i++) {
        int a = r[i][0], b = r[i][1];
        if(pre[a].size() < 2) pre[a].emplace_back(b, i);
        if(pre[b].size() < 2) pre[b].emplace_back(a, i);
    }
    for(int i = 0; i < n; i++) if(pre[i].size() == 1) pre[i].emplace_back(pre[i][0]);
    for(int i = 0; i < n; i++) for(int j = 0; j < (int)pre[i].size(); j++) {
        int v = pre[i][j].x, id = pre[i][j].y;
        if(pre[v][0].y == id) v += n;
        g[v].emplace_back(i + (j ? n : 0));
        ++deg[i + (j ? n : 0)];
    }
    queue<int> Q;
    for(int i = 0; i < 2*n; i++) if(!deg[i]) Q.emplace(i);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int v : g[u]) if(!--deg[v])
            Q.emplace(v);
    }
    int cyc_sz = 0;
    for(int i = 0; i < 2*n; i++) if(deg[i]) ++cyc_sz;

    auto get_dist = [&](int a) {
        vector<bool> chk(n<<1); 
        d[a] = 0, chk[a] = true;
        Q.emplace(a);
        while(!Q.empty()) {
            int u = Q.front(); Q.pop();
            for(int v : g[u]) if(!chk[v])
                chk[v] = true, d[v] = d[u] + 1, Q.emplace(v);
        }
    };
    auto get_ans = [&](int len) {
        int ret = 0;
        for(int i = 0; i < n; i++) {
            if(d[i] > len) continue;
            if(cyc_sz) ret += ((len % cyc_sz) == d[i]);
            else ++ret;
        }
        return ret;
    };
    vector<int> ans(q, 0);
    get_dist(p);
    for(int i = 0; i < q; i++) ans[i] += get_ans(_g[i]);
    get_dist(p + n);
    for(int i = 0; i < q; i++) answer(ans[i] + get_ans(_g[i]));
}

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