oj.uz

Submission #391137

# Submission time Handle Problem Language Result Execution time Memory
391137 2021-04-18T05:12:14 Z arwaeystoamneg Tropical Garden (IOI11_garden) C++17
100 / 100
 2924 ms 37740 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}

#ifndef arwaeystoamneg
#include "garden.h"
#include "gardenlib.h"
#endif

#ifdef arwaeystoamneg
#define MAX_M  1000000
#define MAX_Q  2000

static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;

inline
void my_assert(int e) { if (!e) abort(); }
void read_input()
{
	int i;
	my_assert(3 == scanf("%d %d %d", &N, &M, &P));
	for (i = 0; i < M; i++)
		my_assert(2 == scanf("%d %d", &R[i][0], &R[i][1]));
	my_assert(1 == scanf("%d", &Q));
	for (i = 0; i < Q; i++)
		my_assert(1 == scanf("%d", &G[i]));
	for (i = 0; i < Q; i++)
		my_assert(1 == scanf("%d", &solutions[i]));
}

void answer(int x)
{
	if (answer_count >= Q) {
		printf("Incorrect.  Too many answers.\n");
		exit(0);
	}
	answers[answer_count] = x;
	answer_count++;
}
#endif
const int MAX = 150005;
int n, p, a[2 * MAX], indeg[2 * MAX], cyc[2 * MAX], k = 1, type[2 * MAX], sizes[2 * MAX];
pii win[MAX][2];
vi adj[MAX], back[2 * MAX];
void dfs(int i)
{
	if (type[i])return;
	assert(cyc[i]);
	sizes[k]++;
	type[i] = k;
	dfs(a[i]);
}
int check(pii t, int k)
{
	return k >= t.s && (k - t.s) % t.f == 0;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	n = N;
	p = P;
	F0R(i, M)
	{
		adj[R[i][0]].pb(R[i][1]);
		adj[R[i][1]].pb(R[i][0]);
	}
	F0R(i, n)
	{
		a[2 * i] = 2 * adj[i][0] + (i == adj[adj[i][0]][0]);
		a[2 * i + 1] = 2 * adj[i][min(sz(adj[i]) - 1, 1)] + (i == adj[adj[i][min(sz(adj[i]) - 1, 1)]][0]);
	}
//	F0R(i, 2 * n)cout << i << " " << a[i] << endl;
	F0R(i, 2 * n)indeg[a[i]]++;
	vi todo;
	F0R(i, 2 * n)if (!indeg[i])todo.push_back(i);
	F0R(i, sz(todo))
	{
		indeg[a[todo[i]]]--;
		if (!indeg[a[todo[i]]])todo.push_back(a[todo[i]]);
	}
	F0R(i, 2 * n)if (indeg[i])cyc[i] = 1;
//	cout << endl << endl; F0R(i, 2 * n)cout << i << " " << cyc[i] << endl;
	F0R(i, 2 * n)
	{
		if (cyc[i] && type[i] == 0)
		{
			dfs(i);
			k++;
		}
	}
//	cout << endl << endl; F0R(i, 2 * n)cout << i << " " << type[i] << endl;
//	cout << endl << endl; F0R(i, k)cout << i << " " << sizes[i] << endl;
	F0R(i, 2 * n)back[a[i]].pb(i);
	F0R(i, n)win[i][0] = win[i][1] = { inf,inf };
	int dist[2 * MAX];
	if (cyc[2 * p])
	{
		F0R(i, 2 * n)dist[i] = inf;
		dist[2 * p] = 0;
		vi todo = { 2 * p };
		F0R(i, sz(todo))
		{
			trav(x, back[todo[i]])
			{
				if (dist[x] > dist[todo[i]] + 1)
				{
					dist[x] = dist[todo[i]] + 1;
					todo.pb(x);
				}
			}
		}
		for (int i = 0; i < 2 * n; i += 2)
		{
			if (dist[i] != inf)
			{
				win[i / 2][0] = { sizes[type[2 * p]],dist[i] };
			}
		}
	}
	else
	{
		F0R(i, 2 * n)dist[i] = inf;
		dist[2 * p] = 0;
		vi todo = { 2 * p };
		F0R(i, sz(todo))
		{
			trav(x, back[todo[i]])
			{
				dist[x] = dist[todo[i]] + 1;
				todo.pb(x);
			}
		}
		for (int i = 0; i < 2 * n; i += 2)
		{
			if (dist[i] != inf)
			{
				win[i / 2][0] = { inf,dist[i] };
			}
		}
	}
	if (cyc[2 * p + 1])
	{
		F0R(i, 2 * n)dist[i] = inf;
		dist[2 * p + 1] = 0;
		vi todo = { 2 * p + 1 };
		F0R(i, sz(todo))
		{
			trav(x, back[todo[i]])
			{
				if (dist[x] > dist[todo[i]] + 1)
				{
					dist[x] = dist[todo[i]] + 1;
					todo.pb(x);
				}
			}
		}
		for (int i = 0; i < 2 * n; i += 2)
		{
			if (dist[i] != inf)
			{
				win[i / 2][1] = { sizes[type[2 * p + 1]],dist[i] };
			}
		}
	}
	else
	{
		F0R(i, 2 * n)dist[i] = inf;
		dist[2 * p + 1] = 0;
		vi todo = { 2 * p + 1 };
		F0R(i, sz(todo))
		{
			trav(x, back[todo[i]])
			{
				dist[x] = dist[todo[i]] + 1;
				todo.pb(x);
			}
		}
		for (int i = 0; i < 2 * n; i += 2)
		{
			if (dist[i] != inf)
			{
				win[i / 2][1] = { inf,dist[i] };
			}
		}
	}
	F0R(i, Q)
	{
		int k = G[i];
		int ans = 0;
		F0R(j, n)
		{
			if (check(win[j][0], k))
			{
				ans++;
				assert(!check(win[j][1], k));
			}
			else
			{
				if (check(win[j][1], k))
					ans++;
			}
		}
		answer(ans);
	}
}

#ifdef arwaeystoamneg
int main()
{
	setIO("test1");
	int correct, i;

	read_input();
	answer_count = 0;
	count_routes(N, M, P, R, Q, G);

	if (answer_count != Q) {
		printf("Incorrect.  Too few answers.\n");
		exit(0);
	}

	correct = 1;
	for (i = 0; i < Q; i++)
		if (answers[i] != solutions[i])
			correct = 0;
	if (correct)
		printf("Correct.\n");
	else {
		printf("Incorrect.\n");
		printf("Expected: ");
		for (i = 0; i < Q; i++)
			printf("%d ", solutions[i]);
		printf("\nReturned: ");
		for (i = 0; i < Q; i++)
			printf("%d ", answers[i]);
	}
	return 0;
}


#endif

Compilation message

garden.cpp: In function 'void setIO(std::string)':
garden.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10956 KB Output is correct
2 Correct 7 ms 11084 KB Output is correct
3 Correct 7 ms 11008 KB Output is correct
4 Correct 7 ms 10976 KB Output is correct
5 Correct 6 ms 10876 KB Output is correct
6 Correct 8 ms 11084 KB Output is correct
7 Correct 7 ms 10872 KB Output is correct
8 Correct 7 ms 10956 KB Output is correct
9 Correct 9 ms 11212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10956 KB Output is correct
2 Correct 7 ms 11084 KB Output is correct
3 Correct 7 ms 11008 KB Output is correct
4 Correct 7 ms 10976 KB Output is correct
5 Correct 6 ms 10876 KB Output is correct
6 Correct 8 ms 11084 KB Output is correct
7 Correct 7 ms 10872 KB Output is correct
8 Correct 7 ms 10956 KB Output is correct
9 Correct 9 ms 11212 KB Output is correct
10 Correct 6 ms 10880 KB Output is correct
11 Correct 18 ms 14072 KB Output is correct
12 Correct 35 ms 15816 KB Output is correct
13 Correct 54 ms 26024 KB Output is correct
14 Correct 116 ms 29308 KB Output is correct
15 Correct 144 ms 32408 KB Output is correct
16 Correct 104 ms 25836 KB Output is correct
17 Correct 97 ms 24316 KB Output is correct
18 Correct 37 ms 16548 KB Output is correct
19 Correct 117 ms 29360 KB Output is correct
20 Correct 187 ms 31280 KB Output is correct
21 Correct 106 ms 26032 KB Output is correct
22 Correct 99 ms 23776 KB Output is correct
23 Correct 149 ms 31004 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10956 KB Output is correct
2 Correct 7 ms 11084 KB Output is correct
3 Correct 7 ms 11008 KB Output is correct
4 Correct 7 ms 10976 KB Output is correct
5 Correct 6 ms 10876 KB Output is correct
6 Correct 8 ms 11084 KB Output is correct
7 Correct 7 ms 10872 KB Output is correct
8 Correct 7 ms 10956 KB Output is correct
9 Correct 9 ms 11212 KB Output is correct
10 Correct 6 ms 10880 KB Output is correct
11 Correct 18 ms 14072 KB Output is correct
12 Correct 35 ms 15816 KB Output is correct
13 Correct 54 ms 26024 KB Output is correct
14 Correct 116 ms 29308 KB Output is correct
15 Correct 144 ms 32408 KB Output is correct
16 Correct 104 ms 25836 KB Output is correct
17 Correct 97 ms 24316 KB Output is correct
18 Correct 37 ms 16548 KB Output is correct
19 Correct 117 ms 29360 KB Output is correct
20 Correct 187 ms 31280 KB Output is correct
21 Correct 106 ms 26032 KB Output is correct
22 Correct 99 ms 23776 KB Output is correct
23 Correct 149 ms 31004 KB Output is correct
24 Correct 9 ms 10888 KB Output is correct
25 Correct 118 ms 14204 KB Output is correct
26 Correct 162 ms 16308 KB Output is correct
27 Correct 2528 ms 26812 KB Output is correct
28 Correct 1088 ms 29388 KB Output is correct
29 Correct 2922 ms 31280 KB Output is correct
30 Correct 1628 ms 25904 KB Output is correct
31 Correct 1640 ms 24320 KB Output is correct
32 Correct 180 ms 16572 KB Output is correct
33 Correct 1104 ms 29484 KB Output is correct
34 Correct 2924 ms 32328 KB Output is correct
35 Correct 1756 ms 26072 KB Output is correct
36 Correct 1913 ms 24380 KB Output is correct
37 Correct 858 ms 31064 KB Output is correct
38 Correct 2235 ms 37740 KB Output is correct