Submission #394251

#	Time	Username	Problem	Language	Result	Execution time	Memory
394251		MarcoMeijer	Tropical Garden (IOI11_garden)	C++14	100 / 100	1872 ms	41376 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];
        }
    }

    map<int,int> Static;
    map<int,map<int,int>> Modulo;
    RE(j,N) {
        int u = adj[j][0];
        int times = 0;
        int cg = 0;
        while(functRes[u] != -1) {
            if(functRes[u] == u) {
                Modulo[funct[u]][cg]++;
                break;
            } else {
                if(functRes[functRes[u]] == u) {
                    int totFunct = funct[u] + funct[functRes[u]];
                    Modulo[totFunct][cg]++;
                    times++;
                    if(times == 2)
                        break;
                }
            }
            cg += funct[u];
            if(functRes[functRes[u]] != u && (functRes[u] == -1 || functRes[functRes[u]] != functRes[u])) {
                Static[cg]++;
            }
            u = functRes[u];
        }
    }
    vector<iii> Mod;
    FOR(x,Modulo)
        FOR(y,x.second)
            Mod.push_back({x.fi,y.fi,y.se});

    RE(i,Q) {
        int ans = 0;
        auto it = Static.find(G[i]);
        if(it != Static.end()) ans += it->second;
        FOR(p,Mod) {
            int a, b, c;
            tie(a,b,c) = p;
            if(G[i] < b) continue;
            if((G[i]-b)%a == 0) ans += c;
        }
        answer(ans);
    }
}

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