Submission #394241

#	Time	Username	Problem	Language	Result	Execution time	Memory
394241		MarcoMeijer	Tropical Garden (IOI11_garden)	C++14	49 / 100	49 ms	18976 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()

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]);
    }

    // fill prev
    vector<vi> prev; prev.resize(m);
    RE(i,m) prev[nxt[i]].pb(i);

    vector<bool> visited;
    visited.assign(m,0);
    vi funct; funct.assign(m,-1);
    vi functRes; functRes.assign(m,-1);

    // iniitial queue
    queue<int> q;
    FOR(x,adj[P]) {
        int y = ReverseEdge[x];
        q.push(y);
        visited[y] = 1;
        funct[y] = 1;
        functRes[y] = nxt[y];
    }

    // bfs
    while(!q.empty()) {
        int u=q.front(); q.pop();
        FOR(v,prev[u]) {
            if(visited[v]) continue;
            q.push(v);
            visited[v] = 1;
            funct[v] = funct[u] + 1;
            functRes[v] = functRes[u];
        }
    }

    RE(i,Q) {
        int ans = 0;
        RE(j,N) {
            int u = adj[j][0];
            int ng = G[i];
            int times = 0;
            while(functRes[u] != -1) {
                times++;
                if(times > 5) {
                    break;
                }
                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