oj.uz

Submission #551234

# Submission time Handle Problem Language Result Execution time Memory
551234 2022-04-20T06:11:43 Z ymm Tropical Garden (IOI11_garden) C++17
49 / 100
 116 ms 42676 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<int> vmod[2*N];
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 {
		Loop (i,0,cycs)
			vmod[i].clear();
		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 8 ms 14852 KB Output is correct
2 Correct 8 ms 14804 KB Output is correct
3 Correct 8 ms 14856 KB Output is correct
4 Correct 9 ms 15828 KB Output is correct
5 Correct 8 ms 15876 KB Output is correct
6 Correct 8 ms 14932 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 12 ms 14708 KB Output is correct
9 Correct 12 ms 14820 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14852 KB Output is correct
2 Correct 8 ms 14804 KB Output is correct
3 Correct 8 ms 14856 KB Output is correct
4 Correct 9 ms 15828 KB Output is correct
5 Correct 8 ms 15876 KB Output is correct
6 Correct 8 ms 14932 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 12 ms 14708 KB Output is correct
9 Correct 12 ms 14820 KB Output is correct
10 Correct 9 ms 14676 KB Output is correct
11 Correct 18 ms 16284 KB Output is correct
12 Correct 26 ms 17108 KB Output is correct
13 Correct 51 ms 32668 KB Output is correct
14 Correct 76 ms 22560 KB Output is correct
15 Correct 116 ms 23360 KB Output is correct
16 Correct 104 ms 21196 KB Output is correct
17 Runtime error 93 ms 42676 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 8 ms 14852 KB Output is correct
2 Correct 8 ms 14804 KB Output is correct
3 Correct 8 ms 14856 KB Output is correct
4 Correct 9 ms 15828 KB Output is correct
5 Correct 8 ms 15876 KB Output is correct
6 Correct 8 ms 14932 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 12 ms 14708 KB Output is correct
9 Correct 12 ms 14820 KB Output is correct
10 Correct 9 ms 14676 KB Output is correct
11 Correct 18 ms 16284 KB Output is correct
12 Correct 26 ms 17108 KB Output is correct
13 Correct 51 ms 32668 KB Output is correct
14 Correct 76 ms 22560 KB Output is correct
15 Correct 116 ms 23360 KB Output is correct
16 Correct 104 ms 21196 KB Output is correct
17 Runtime error 93 ms 42676 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -