Submission #1026883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026883		onbert	Tropical Garden (IOI11_garden)	C++17	100 / 100	1406 ms	38576 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150005, maxm = 150005, INF = 1e9;
int n, m, p;
vector<int> adj[maxn];
int vis[maxn][2];
int dist[maxn][2][2];
vector<pair<int,int>> track;
int cyclesz[2] = {INF, INF};

int dfs(int u) {
    int id = (track.size()>0 && track.back().first==adj[u][0] && adj[u].size()>1);
    // cout << u << " " << id << " " << vis[u][id] << endl;
    if (vis[u][id]==-3) return id;
    if (vis[u][id]==-2) {
        // cout << u << " " << id << endl;
        vector<pair<int,int>> c;
        reverse(track.begin(), track.end());
        for (auto [i, j]:track) {
            c.push_back({i, j});
            if (i==u && j==id) break;
        }
        int sz = c.size(), pos = -1;
        for (int i=0;i<sz;i++) if (c[i].first==p && c[i].second==0) pos = i;
        if (pos!=-1) {
            cyclesz[0] = sz;
            for (int i=0;i<sz;i++) {
                int cur = (i+pos)%sz;
                dist[c[cur].first][c[cur].second][0] = i;
            }
        }

        pos = -1;
        for (int i=0;i<sz;i++) if (c[i].first==p && c[i].second==1) pos = i;
        if (pos!=-1) {
            // cout << pos << endl;
            cyclesz[1] = sz;
            for (int i=0;i<sz;i++) {
                int cur = (i+pos)%sz;
                dist[c[cur].first][c[cur].second][1] = i;
                // cout << "cost " << c[cur].first << " " << c[cur].second << " " << i << endl;
            }
        }
        return id;
    }
    vis[u][id] = -2;
    track.push_back({u, id});
    int v = adj[u][id];
    int nxt = dfs(v);
    for (int i=0;i<=1;i++) {
        if (dist[u][id][i]==-1 && dist[v][nxt][i]!=-1) dist[u][id][i] = dist[v][nxt][i] + 1;
    }
    if (u==p) dist[u][id][id] = 0;
    vis[u][id] = -3;
    return id;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    n = N, m = M, p = P;
    for (int i=0;i<m;i++) {
        int u = R[i][0], v = R[i][1];
        if (adj[u].size()<2) adj[u].push_back(v);
        if (adj[v].size()<2) adj[v].push_back(u);
    }
    for (int i=0;i<n;i++) vis[i][0] = vis[i][1] = dist[i][0][0] = dist[i][1][0] = dist[i][0][1] = dist[i][1][1] = -1;
    for (int i=0;i<n;i++) if (vis[i][0]==-1) {
        track.clear();
        dfs(i);
    }
    // cout << cyclesz[0] << " " << cyclesz[1] << endl;
    for (int i=0;i<Q;i++) {
        int x = G[i];
        int32_t ans = 0;
        for (int i=0;i<n;i++) {
            bool add = false;
            for (int j=0;j<=1;j++) {
                if (dist[i][0][j]!=-1 && x>=dist[i][0][j] && (x-dist[i][0][j])%cyclesz[j]==0) add = true;
            }
            ans += add;
        }
        answer(ans);
    }
}

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