Submission #391127

#	Time	Username	Problem	Language	Result	Execution time	Memory
391127		arwaeystoamneg	Tropical Garden (IOI11_garden)	C++17	49 / 100	55 ms	26868 KiB

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][1] = { 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][0] = { 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 (stderr)

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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31