Submission #393355

#	Time	Username	Problem	Language	Result	Execution time	Memory
393355		MarcoMeijer	Tropical Garden (IOI11_garden)	C++14	49 / 100	71 ms	29368 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    // create graph
    vector<vi> adj; adj.resize(N);
    int m=0;
    vi U, V, ReverseEdge;
    RE(i,M) {
        U.push_back(R[i][0]); V.push_back(R[i][1]);
        adj[U[m]].push_back(m); ReverseEdge.push_back(m+1); m++;
        U.push_back(R[i][1]); V.push_back(R[i][0]);
        adj[U[m]].push_back(m); ReverseEdge.push_back(m-1); m++;
    }

    // fill next
    vi nxt;
    RE(i,m) {
        bool found = 0;
        FOR(v,adj[V[i]]) {
            if(v == ReverseEdge[i]) continue;
            nxt.push_back(v);
            found = 1;
            break;
        }
        if(!found)
            nxt.push_back(ReverseEdge[i]);
    }

    vector<bool> partOfCycle, visited, newlyVisited;
    partOfCycle.assign(m,0); visited.assign(m,0); newlyVisited.assign(m,0);
    vi funct; funct.assign(m,-1);
    vi functRes; functRes.assign(m,-1);
    int cycleLength, ansStart;
    function<void(int)> makePartOfCycle = [&](int u) {
        if(partOfCycle[u]) return;
        partOfCycle[u] = 1;
        cycleLength++;
        if(U[u] == P)
            ansStart = u;
        makePartOfCycle(nxt[u]);
    };
    function<void(int)> fillAnsCycle = [&](int u) {
        if(funct[u] != -1) return;
        funct[u] = cycleLength--;
        functRes[u] = ansStart;
        fillAnsCycle(nxt[u]);
    };
    function<void(int)> fillCycle = [&](int u) {
        if(newlyVisited[u]) {
            cycleLength = 0;
            ansStart = -1;
            makePartOfCycle(u);
            if(ansStart != -1) {
                fillAnsCycle(ansStart);
            }
            newlyVisited[u] = 0;
            return;
        }
        if(visited[u]) return;
        newlyVisited[u] = 1;
        visited[u] = 1;
        fillCycle(nxt[u]);
        if(funct[u] == -1) {
            if(U[nxt[u]] == P) funct[u] = 1, functRes[u] = nxt[u];
            else {
                if(funct[nxt[u]] != -1)
                    funct[u] = funct[nxt[u]]+1, functRes[u] = functRes[nxt[u]];
            }
        }
        newlyVisited[u] = 0;
    };
    RE(i,m) {
        if(visited[i]) continue;
        fillCycle(i);
    }

    RE(i,Q) {
        int ans = 0;
        RE(j,N) {
            int u = adj[j][0];
            int ng = G[i];
            while(functRes[u] != -1) {
                if(functRes[u] == u) {
                    if((ng%funct[u]) == 0) ans++;
                    break;
                }
                if(ng < funct[u]) break;
                ng -= funct[u];
                u = functRes[u];
                if(ng == 0) {
                    ans++;
                    break;
                }
            }
        }
        answer(ans);
    }
}

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