oj.uz

Submission #551226

# Submission time Handle Problem Language Result Execution time Memory
551226 2022-04-20T06:06:06 Z ymm Tropical Garden (IOI11_garden) C++17
49 / 100
 75 ms 29556 KB 
///
///   There's a reason for your defeat, DIO. One simple reason...
///   You pissed me off.
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#ifndef DARD
#include "garden.h"
#include "gardenlib.h"
#else
void answer(int x)
{
	cout << x << ' ';
}
#endif

const int N = 150'010;
vector<int> T[2*N];
int A[2*N];
int deg[2*N], cnt[2*N];

void add_edge(int v, int u)
{
	A[v] = u;
	T[u].push_back(v);
}

int ans[N];
int q, g[N];

bool cyc[2*N];

void dfs(int v, int d)
{
	cnt[d] += v >= N;
	for (int u : T[v])
		dfs(u, d+1);
}

vector<vector<int>> vmod;
int cycs;

void dfs2(int v, int d, int rt)
{
	if (v >= N)
		vmod[d%cycs].push_back(d);
	for (int u : T[v])
		if (u != rt)
			dfs2(u, d+1, rt);
}

void solve(int v)
{
	memset(cyc, 0, sizeof(cyc));
	int u = v;
	cycs = 0;
	do {
		cyc[u] = 1;
		u = A[u];
		++cycs;
	} while (!cyc[u]);
	if (u != v) {
		memset(cnt, 0, sizeof(cnt));
		dfs(v, 0);
		Loop (i,0,q)
			ans[i] += cnt[g[i]];
	} else {
		vmod.clear();
		vmod.resize(cycs);
		dfs2(v, 0, v);
		Loop (i,0,cycs)
			sort(vmod[i].begin(), vmod[i].end());
		Loop (i,0,q) {
			int gm = g[i]%cycs;
			ans[i] += upper_bound(vmod[gm].begin(),
			              vmod[gm].end(), g[i]) - vmod[gm].begin();
		}
	}
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[])
{
	Loop (i,0,m) {
		deg[r[i][0]]++;
		deg[r[i][1]]++;
	}
	Loop (i,0,m) {
		for (auto [v, u] : {pii{r[i][0], r[i][1]}, pii{r[i][1], r[i][0]}}) {
			if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] == 0) // F F
				add_edge(v, u);
			if ((cnt[v] == 1 || deg[v] == 1) && cnt[u] != 0) // F nF
				add_edge(v, u+N);
			if (cnt[v] == 0 && cnt[u] == 0) // nF F
				add_edge(v+N, u);
			if (cnt[v] == 0 && cnt[u] != 0) // nF nF
				add_edge(v+N, u+N);
		}
		cnt[r[i][0]]++;
		cnt[r[i][1]]++;
	}
	::q = q;
	Loop (i,0,q) ::g[i] = g[i];
	solve(p);
	solve(p+N);
	Loop (i,0,q)
		answer(ans[i]);
}

#ifdef DARD
int main()
{
//	int constexpr n = 6;
//	int constexpr m = 6;
//	int constexpr p = 0;
//	int constexpr q = 1;
//	int g[q] = {3};
//	int r[m][2] = {{1,2}, {0,1}, {0,3}, {3,4}, {4,5}, {1,5}};
	int constexpr n = 5;
	int constexpr m = 5;
	int constexpr p = 2;
	int constexpr q = 2;
	int g[q] = {3, 1};
	int r[m][2] = {{1,0}, {1,2}, {3,2}, {1,3}, {4,2}};
	count_routes(n, m, p, r, q, g);
	cout << '\n';
}
#endif

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7764 KB Output is correct
2 Correct 4 ms 7796 KB Output is correct
3 Correct 5 ms 7764 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 6 ms 7764 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7764 KB Output is correct
2 Correct 4 ms 7796 KB Output is correct
3 Correct 5 ms 7764 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 6 ms 7764 KB Output is correct
10 Correct 4 ms 7652 KB Output is correct
11 Correct 12 ms 9216 KB Output is correct
12 Correct 23 ms 10024 KB Output is correct
13 Correct 59 ms 29556 KB Output is correct
14 Correct 64 ms 15604 KB Output is correct
15 Correct 75 ms 16192 KB Output is correct
16 Correct 63 ms 14176 KB Output is correct
17 Runtime error 67 ms 28444 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7764 KB Output is correct
2 Correct 4 ms 7796 KB Output is correct
3 Correct 5 ms 7764 KB Output is correct
4 Correct 6 ms 8788 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 6 ms 7764 KB Output is correct
10 Correct 4 ms 7652 KB Output is correct
11 Correct 12 ms 9216 KB Output is correct
12 Correct 23 ms 10024 KB Output is correct
13 Correct 59 ms 29556 KB Output is correct
14 Correct 64 ms 15604 KB Output is correct
15 Correct 75 ms 16192 KB Output is correct
16 Correct 63 ms 14176 KB Output is correct
17 Runtime error 67 ms 28444 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -