답안 #391137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391137	2021-04-18T05:12:14 Z	arwaeystoamneg	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	2924 ms	37740 KB

garden

// 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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