Submission #559272

#	Time	Username	Problem	Language	Result	Execution time	Memory
559272		ngpin04	Tropical Garden (IOI11_garden)	C++14	100 / 100	103 ms	34200 KiB

garden

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
const int Nmax = 3e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

#include "garden.h"
#include "gardenlib.h"
//#include "grader.cpp"

vector <int> adj[Nmax];
vector <int> val[Nmax];

pair <int, int> ed[Nmax];
pair <int, int> pir[Nmax];

int ptr[Nmax];
int ans[Nmax];
int qr[Nmax];
int n,m,p,q;

bool cyc[Nmax];

void addEdge(int u, int v) {
    // cerr << u << " " << v << "\n";
    ptr[u] = v;
    adj[v].push_back(u);
}

void build() {
    for (int i = 0; i < n; i++)
        pir[i] = mp(-1, -1);

    for (int i = 0; i < m; i++) {
        int u = ed[i].fi;
        int v = ed[i].se;

        if (pir[u].fi == -1)
            pir[u].fi = v;
        else if (pir[u].se == -1)
            pir[u].se = v;

        if (pir[v].fi == -1)
            pir[v].fi = u;
        else if (pir[v].se == -1)
            pir[v].se = u;        
    }

    for (int i = 0; i < n; i++) {
        int j;
        j = pir[i].fi;
        if (pir[j].fi == i)
            addEdge(i, j + n);
        else
            addEdge(i, j);

        j = pir[i].se;
        if (j == -1) {
            addEdge(i + n, ptr[i]);
        } else {
            if (pir[j].fi == i)
                addEdge(i + n, j + n);
            else
                addEdge(i + n, j);
        }
    }
}

void dfs(int u, int d, vector <int> &cnt) {
    if (u < n)
        cnt[d]++;
    for (int v : adj[u]) 
        dfs(v, d + 1, cnt);
}

void dfs1(int u, int d, int sz) {
    if (u < n)
        val[d % sz].push_back(d);
    for (int v : adj[u])
        if (!cyc[v])
            dfs1(v, d + 1, sz);
}

void solve(int s) {
    memset(cyc, 0, sizeof(cyc));
    int v = s;
    int sz = 0;
    while (!cyc[ptr[v]]) {
        v = ptr[v];
        cyc[v] = true;
        sz++;
    }

    for (int i = 0; i < sz; i++)
        val[i].clear();
    
    if (v != s) {
        vector <int> cnt(2 * n, 0);
        dfs(s, 0, cnt);

        for (int i = 0; i < q; i++)
            if (qr[i] < 2 * n)
                ans[i] += cnt[qr[i]];
    } else {
        for (int v = s, rep = 1, cur = 0; rep <= sz; v = ptr[v], rep++) {
            dfs1(v, cur, sz);

            cur--;
            if (cur < 0)
                cur = sz - 1;
        }
        for (int i = 0; i < sz; i++)
            sort(ALL(val[i]));

        for (int i = 0; i < q; i++) {
            int k = qr[i];
            int v = k % sz;
            ans[i] += upper_bound(ALL(val[v]), k) - val[v].begin();
        }
    }


}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    m = M;
    p = P;
    q = Q;
    for (int i = 0; i < m; i++)
        ed[i] = mp(R[i][0], R[i][1]);
    for (int i = 0; i < q; i++)
        qr[i] = G[i];

    build();
    solve(p);
    solve(p + n);

    for (int i = 0; i < q; i++)
        answer(ans[i]);
}   

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