Submission #390135

#	Time	Username	Problem	Language	Result	Execution time	Memory
390135		AriaH	Tropical Garden (IOI11_garden)	C++11	Compilation error	0 ms	0 KiB

garden

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int Lev[N], mark[N], Md[N];

vector < int > cyc, lev[N], G[N], adj[N], adt[N], mp[N];

inline void add(int v, int u)
{
	printf("yal %d -> %d\n", v, u);
	adj[v].push_back(u);
	adt[u].push_back(v);
}

void dfs(int v, int H = 0)
{
	lev[H].push_back(v);
	Lev[H] += (v & 1);
	for(auto u : adt[v])
	{
		dfs(u, H + 1);
	}
}

void DFS(int v, int root, int H)
{
	int cost = H + Md[root];
	if(v & 1) mp[cost % SZ(cyc)].push_back(cost);
	for(auto u : adt[v])
	{
		if(mark[u]) continue;
		DFS(u, root, H + 1);
	}
}

void count_routs(int n, int m, int st, int E[][2], int q, int Q[])
{
	for(int i = 0; i < m; i ++)
	{
		int v = E[i][0], u = E[i][1];
		G[v].push_back(u);
		G[u].push_back(v);
	}
	for(int i = 0; i < n; i ++)
	{
		if(SZ(G[i]) > 1)
		{
			int u = G[i][1];
			if(G[u][0] == i) add(i << 1, u << 1);
			else add(i << 1, u << 1 | 1);
		}
		else
		{
			int u = G[i][0];
			if(G[u][0] == i) add(i << 1, u << 1);
			else add(i << 1, u << 1 | 1);
		}
		int u = G[i][0];
		if(G[u][0] == i) add(i << 1 | 1, u << 1);
		else add(i << 1 | 1, u << 1 | 1);
	}
	int node = st << 1 | 1;
	while(!mark[node])
	{
		mark[node] = 1;
		node = adj[node][0];
		cyc.push_back(node);
	}
	if(node != st << 1 | 1)
	{
		dfs(st << 1 | 1);
		for(int i = 0; i < q; i ++)
		{
			if(Q[i] >= N)
			{
				printf("0\n");
				continue;
			}
			printf("%d\n", Lev[Q[i]]);
		}
		return;
	}
	///printf("alive\n");
	reverse(all(cyc));
	for(int i = 0; i < SZ(cyc); i ++)
	{
		Md[cyc[i]] = i;
		DFS(cyc[i], cyc[i], 0);
	}
	for(int i = 0; i < q; i ++)
	{
		int T = Q[i] % SZ(cyc);
		int tot = upper_bound(all(mp[T]), Q[i]) - mp[T].begin();
		printf("%d\n", tot);
	}
}

/*int n, m, st, q, E[N][2], Q[N];

int main()
{
	scanf("%d%d%d%d", &n, &m, &st, &q);
	for(int i = 0; i < m; i ++)
	{
		scanf("%d%d", &E[i][0], &E[i][1]);
	}
	for(int i = 0; i < q; i ++) scanf("%d", &Q[i]);
	count_routs(n, m, st, E, q, Q);
    return 0;
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

garden.cpp: In function 'void count_routs(int, int, int, int (*)[2], int, int*)':
garden.cpp:92:10: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   92 |  if(node != st << 1 | 1)
      |     ~~~~~^~~~~~~~~~
/tmp/ccPTc8Mk.o: In function `main':
grader.cpp:(.text.startup+0x3b): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status