Submission #753937

#	Time	Username	Problem	Language	Result	Execution time	Memory
753937		lukameladze	Tropical Garden (IOI11_garden)	C++14	69 / 100	5053 ms	63144 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int MX = 3e5 + 5;
int n,m,q,p,k[MX],dist[MX],ans[MX], in_cycle, cycle_l,best[MX], s_best[MX],ans1[MX];
vector <int> v[MX], vr[MX],n_g[MX];
vector <pii> g[MX];
int can(int i) {
    return 2 * i - 1;
}
int cnnt(int i) {
    return 2 * i;
}
 
void bfs(int a) {
    queue <int> q;
    int pp = a;
    for (int i = 1; i <= 2 * n; i++) {
        dist[i] = -1;
    }
    q.push(a); dist[a] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int to : vr[x]) {
            if (to == pp) {
                in_cycle = 1;
                cycle_l = dist[x] + 1;
            }
            if (dist[to] == -1) {
                dist[to] = dist[x] + 1;
                q.push(to);
            }
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N; m = M; p = P; p++; q = Q;
	for (int i = 1; i <= m; i++) {
		int a, b;
		a = R[i - 1][0]; b = R[i - 1][1];
		a++; b++;
		g[a].pb({i - 1, b});
		g[b].pb({i - 1, a});
	}
    for (int i = 1; i <= q; i++) {
        k[i] = G[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
        best[i] = g[i][0].s;
        s_best[i] = ((int)g[i].size() == 1 ? g[i][0].s : g[i][1].s);
    }
    for (int i = 1; i <= n; i++) {
        int a = i, b = best[i];
        if (best[b] == a) n_g[can(a)].pb(cnnt(b));
        else n_g[can(a)].pb(can(b));
 
        b = s_best[i];
        if (best[b] == a) n_g[cnnt(a)].pb(cnnt(b));
        else n_g[cnnt(a)].pb(can(b));
    }
    for (int i = 1; i <= n; i++) {
        v[i].clear();
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (int x : n_g[i]) {
//            cout<<i<<" -- "<<x<<"\n";
            v[i].pb(x); vr[x].pb(i);
        }
    }
    bfs(can(p));
    for (int i = 1; i <= n; i++) {
        if (dist[can(i)] == -1) continue;
        ans[dist[can(i)]]++;
    }
    int fin = in_cycle, fl = cycle_l;
/*    if (in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans[i] += ans[i - cycle_l];
        }
    }*/
    in_cycle = 0;
    bfs(cnnt(p));
    int c_in = in_cycle, sl = cycle_l;
    for (int i = 1; i <= n; i++) {
        if (dist[can(i)] == -1) continue;
        ans1[dist[can(i)]]++;
    }
/*    if(in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans1[i] += ans1[i - cycle_l];
        }
    }*/
	for(int i = 1; i <= q; i++) {
		int res = 0;
		for (int j = 0; j <= min(k[i], n); j++) {
			if (j == k[i]) {
				res += ans[j];
			} else if (fin && k[i] % fl == j % fl) {
				res += ans[j];
			}
		}
		for (int j = 0; j <= min(k[i], n); j++) {
			if (j == k[i]) res += ans1[j];
			else if (c_in && k[i] % sl == j % sl) res += ans1[j];
		}
		answer(res);
	}
}

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