oj.uz

Submission #250067

# Submission time Handle Problem Language Result Execution time Memory
250067 2020-07-16T19:17:12 Z mode149256 Tropical Garden (IOI11_garden) C++14
0 / 100
 12 ms 21632 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;
	for (int i = 1; i < 2 * N; i += 2)
	{
		if (dis[0][i] != MOD) {
			kiek0[dis[0][i]]++;
			// visi.emplace_back();
		}
		if (dis[1][i] != MOD) {
			kiek1[dis[1][i]]++;
			// visi.emplace_back(dis[1][i]);
		}
	}

	// print(visi);
	for (int i = 0; i < Q; i++) {
		int ret = kiek0[G[i] % len0] + kiek1[G[i] % len1];
		answer(ret);
	}
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21632 KB Output isn't correct
2 Halted 0 ms 0 KB -