Submission #834894

#	Time	Username	Problem	Language	Result	Execution time	Memory
834894		Magikarp4000	Tropical Garden (IOI11_garden)	C++17	100 / 100	132 ms	48456 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 3e5+10;
int n,m,tgt,q;
vector<PII> adj[MAXN];
int f[MAXN], pos[2], d[MAXN][2], cnt[MAXN][2], start[2], len[2];
int res[MAXN], rogue[MAXN];
vector<int> r[MAXN];
bool z[MAXN][2], cyc[MAXN][2], z1[MAXN][2];

int dfs(int s, int idx) {
    int num = 0;
    while (!z[s][idx]) {
        z[s][idx] = 1;
        s = f[s];
        num++;
    }
    return s;
}

int dfs1(int s, int idx) {
    bool begun = 0;
    int num = 0;
    while (!begun || s != start[idx]) {
        begun = 1;
        if (s == tgt) pos[0] = num;
        else if (s == tgt+n) pos[1] = num;
        cyc[s][idx] = 1;
        num++;
        s = f[s];
    }
    return num;
}

void dfs2(int s, int idx) {
    if (pos[idx] == -1) return;
    bool begun = 0;
    int num = 0;
    while (!begun || s != start[idx]) {
        begun = 1;
        d[s][idx] = pos[idx] >= num ? pos[idx]-num : pos[idx]-num+len[idx];
        num++;
        s = f[s];
    }
}

void dfs3(int s, int idx) {
    if (pos[idx] == -1) return;
    stack<int> st;
    while (d[s][idx] == -1) {
        st.push(s);
        s = f[s];
    }
    int num = d[s][idx]+1;
    while (!st.empty()) {
        int cur = st.top();
        st.pop();
        d[cur][idx] = num++;
    }
}

void dfs4(int s, int dist) {
    if (s < n) rogue[dist]++;
    FORX(u,r[s]) dfs4(u,dist+1);
}

void dfs5(int s, int idx) {
    if (z1[s][idx]) return;
    z1[s][idx] = 1;
    FORX(u,r[s]) dfs5(u,idx);
    dfs5(f[s],idx);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N, m = M, tgt = P, q = Q;
    FOR(i,0,m) {
        int a = R[i][0], b = R[i][1];
        adj[a].PB({i,b});
        adj[b].PB({i,a});
    }
    FOR(i,0,n) sort(ALL(adj[i]));
    FOR(i,0,n) {
        int best = adj[i][0].S;
        if (adj[best][0].S == i) f[i] = best+n;
        else f[i] = best;
        int best1 = adj[i].size() <= 1 ? best : adj[i][1].S;
        if (adj[best1][0].S == i) f[i+n] = best1+n;
        else f[i+n] = best1;
    }
    FOR(i,0,n*2) r[f[i]].PB(i);
    FOR(i,0,n*2) {
        FOR(j,0,2) d[i][j] = -1;
    }
    pos[0] = pos[1] = -1;
    len[0] = len[1] = 1;
    FOR(j,0,2) {
        int cur = j == 0 ? tgt : tgt+n;
        dfs5(cur,j);
        start[j] = dfs(cur,j);
        len[j] = dfs1(start[j],j);
        dfs2(start[j],j);
        FOR(i,0,n*2) if (z1[i][j]) dfs3(i,j);
        if (!cyc[cur][j]) dfs4(cur,0);
    }
    vector<int> val[2];
    FOR(j,0,2) {
        FOR(i,0,n) {
            if (d[i][j] != -1) {
                val[j].PB(d[i][j]);
                cnt[d[i][j]%len[j]][j]++;
            }
        }
        sort(ALL(val[j]), greater<int>());
    }
    int v0n = val[0].size(), v1n = val[1].size();
    vector<PII> qrs;
    FOR(i,0,q) qrs.PB({G[i],i});
    sort(ALL(qrs), greater<PII>());
    int j = 0, k = 0;
    FOR(i,0,q) {
        int x = qrs[i].F, idx = qrs[i].S;
        while (j < v0n && val[0][j] > x) cnt[val[0][j++]%len[0]][0]--;
        while (k < v1n && val[1][k] > x) cnt[val[1][k++]%len[1]][1]--;
        int extra = x >= MAXN ? 0 : rogue[x];
        res[idx] = cnt[x%len[0]][0]+cnt[x%len[1]][1]+extra;
    }
    FOR(i,0,q) answer(res[i]);
}

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