oj.uz

Submission #250069

# Submission time Handle Problem Language Result Execution time Memory
250069 2020-07-16T19:27:20 Z mode149256 Tropical Garden (IOI11_garden) C++14
69 / 100
 228 ms 49236 KB 
/*input

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

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 300101;


vii all(MX);
int n, m, p;

vii edges(MX);
vii revEdges(MX);
vii dis(2);

// 0 - negaliu ilgiausio // atejo is ilgiausio
// 1 - galiu ilgiausia
void makeEdges() {
	for (int i = 0; i < n; ++i)
	{
		// 0
		int k;
		if (all[i].size() == 2) {
			k = all[i][1];
		} else {
			k = all[i][0];
		}

		edges[i * 2].emplace_back(2 * k + int(all[k][0] != i));
		revEdges[2 * k + int(all[k][0] != i)].emplace_back(i * 2);
		// printf("%d %d\n", i * 2, 2 * k + int(all[k][0] != i));

		k = all[i][0];
		edges[i * 2 + 1].emplace_back(2 * k + int(all[k][0] != i));
		revEdges[2 * k + int(all[k][0] != i)].emplace_back(i * 2 + 1);
		// printf("%d %d\n", i * 2 + 1, 2 * k + int(all[k][0] != i));
	}
}

void makeDis() {
	dis[0] = dis[1] = vi(2 * n, MOD);

	dis[0][2 * p] = 0;

	queue<int> q;
	q.push(2 * p);

	while (q.size()) {
		int c = q.front(); q.pop();

		for (auto u : revEdges[c]) {
			if (dis[0][u] == MOD) {
				dis[0][u] = dis[0][c] + 1;
				q.push(u);
			}
		}
	}

	q.push(2 * p + 1);
	dis[1][2 * p + 1] = 0;

	while (q.size()) {
		int c = q.front(); q.pop();

		for (auto u : revEdges[c]) {
			if (dis[1][u] == MOD) {
				dis[1][u] = dis[1][c] + 1;
				q.push(u);
			}
		}
	}
}

int start;
int len = 0;
vb been;

bool find_cycle(int x) {
	if (x == start and been[start]) {
		// found
		return true;
	}

	int u = edges[x][0];
	if (!been[u]) {
		been[u] = true;
		if (find_cycle(u)) {
			len++;
			return true;
		}
	}

	return false;
}

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

		if (all[a].size() < 2)
			all[a].emplace_back(b);
		if (all[b].size() < 2)
			all[b].emplace_back(a);
	}

	makeEdges();
	makeDis();

	int len0 = 0;
	int len1 = 0;
	{
		been = vb(2 * N, false);
		start = 2 * p;
		len = 0;
		find_cycle(2 * p);
		// assert(len);
		len0 = (len ? len : MOD);
		// printf("len = %d\n", len);

		been = vb(2 * N, false);
		start = 2 * p + 1;
		len = 0;
		find_cycle(2 * p + 1);
		// assert(len);
		len1 = (len ? len : MOD);
		// printf("len = %d\n", len);
	}

	// vi visi;
	map<int, int> kiek0;
	map<int, int> kiek1;
	vi visi0;
	vi visi1;

	for (int i = 1; i < 2 * N; i += 2)
	{
		if (dis[0][i] != MOD) {
			// kiek0[dis[0][i]]++;
			visi0.emplace_back(dis[0][i]);
			// printf("0 dis = %d\n", dis[0][i]);
			// visi.emplace_back();
		}
		if (dis[1][i] != MOD) {
			// kiek1[dis[1][i]]++;
			// printf("1 dis = %d\n", dis[1][i]);
			visi1.emplace_back(dis[1][i]);
			// visi.emplace_back(dis[1][i]);
		}
	}
	sort(visi0.begin(), visi0.end());
	sort(visi1.begin(), visi1.end());

	vi ind(Q); for (int i = 0; i < Q; ++i) ind[i] = i;

	sort(ind.begin(), ind.end(), [&](const int &a, const int &b) {
		return G[a] < G[b];
	});

	vi ats(Q);
	int j0 = 0;
	int j1 = 0;

	for (int i = 0; i < Q; ++i)
	{
		while (j0 < (int)visi0.size() and visi0[j0] <= G[ind[i]]) {
			kiek0[(visi0[j0]) % len0]++;
			j0++;
		}
		while (j1 < (int)visi1.size() and visi1[j1] <= G[ind[i]]) {
			kiek1[(visi1[j1]) % len1]++;
			j1++;
		}
		ats[ind[i]] = kiek0[G[i] % len0] + kiek1[G[i] % len1];
	}
	// print(visi);
	// printf("len0 = %d, len1 = %d\n", len0, len1);
	for (int i = 0; i < Q; i++) {
		// int ret = kiek0[G[i] % len0] + kiek1[G[i] % len1];
		answer(ats[i]);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 13 ms 21632 KB Output is correct
3 Correct 13 ms 21632 KB Output is correct
4 Correct 12 ms 21504 KB Output is correct
5 Correct 12 ms 21504 KB Output is correct
6 Correct 13 ms 21632 KB Output is correct
7 Correct 12 ms 21504 KB Output is correct
8 Correct 13 ms 21632 KB Output is correct
9 Correct 15 ms 21760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 13 ms 21632 KB Output is correct
3 Correct 13 ms 21632 KB Output is correct
4 Correct 12 ms 21504 KB Output is correct
5 Correct 12 ms 21504 KB Output is correct
6 Correct 13 ms 21632 KB Output is correct
7 Correct 12 ms 21504 KB Output is correct
8 Correct 13 ms 21632 KB Output is correct
9 Correct 15 ms 21760 KB Output is correct
10 Correct 12 ms 21504 KB Output is correct
11 Correct 27 ms 25344 KB Output is correct
12 Correct 48 ms 28028 KB Output is correct
13 Correct 135 ms 49236 KB Output is correct
14 Correct 192 ms 43896 KB Output is correct
15 Correct 228 ms 45196 KB Output is correct
16 Correct 162 ms 38280 KB Output is correct
17 Correct 137 ms 35976 KB Output is correct
18 Correct 45 ms 28024 KB Output is correct
19 Correct 167 ms 43888 KB Output is correct
20 Correct 202 ms 44696 KB Output is correct
21 Correct 151 ms 38132 KB Output is correct
22 Correct 152 ms 35832 KB Output is correct
23 Correct 189 ms 45944 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 13 ms 21632 KB Output is correct
3 Correct 13 ms 21632 KB Output is correct
4 Correct 12 ms 21504 KB Output is correct
5 Correct 12 ms 21504 KB Output is correct
6 Correct 13 ms 21632 KB Output is correct
7 Correct 12 ms 21504 KB Output is correct
8 Correct 13 ms 21632 KB Output is correct
9 Correct 15 ms 21760 KB Output is correct
10 Correct 12 ms 21504 KB Output is correct
11 Correct 27 ms 25344 KB Output is correct
12 Correct 48 ms 28028 KB Output is correct
13 Correct 135 ms 49236 KB Output is correct
14 Correct 192 ms 43896 KB Output is correct
15 Correct 228 ms 45196 KB Output is correct
16 Correct 162 ms 38280 KB Output is correct
17 Correct 137 ms 35976 KB Output is correct
18 Correct 45 ms 28024 KB Output is correct
19 Correct 167 ms 43888 KB Output is correct
20 Correct 202 ms 44696 KB Output is correct
21 Correct 151 ms 38132 KB Output is correct
22 Correct 152 ms 35832 KB Output is correct
23 Correct 189 ms 45944 KB Output is correct
24 Incorrect 13 ms 21504 KB Output isn't correct
25 Halted 0 ms 0 KB -