Submission #1146593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146593		sano	Tropical Garden (IOI11_garden)	C++20	49 / 100	93 ms	42428 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 10000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;




vec<vec<pii>> g;

vec<vec<vec<ll>>> dist;
vec<vec<bool>> bol;
/*
void answer(ll x) {
	cout << x << '\n';
	return;
}
*/

ll dfs(ll x, ll pr, ll typ) {
	if (g[x].size() == 1) pr = -1;
	For(i, g[x].size()) {
		if (g[x][i].ss == pr) continue;
		if (bol[x][i]) return dist[x][i][typ];
		bol[x][i] = 1;
		dist[x][i][typ] = dfs(g[x][i].ff, g[x][i].ss, typ) + 1;
		return dist[x][i][typ];
	}
}

void count_routes(int n, int m, int p, int r[][2], int q, int pq[]) {
	g.resize(n);
	dist.resize(n, vec<vec<ll>>(2, vec<ll>(2, (-1) * NEK)));
	For(i, m) {
		if (g[r[i][0]].size() != 2) {
			g[r[i][0]].push_back({ r[i][1], i });
		}
		if (g[r[i][1]].size() != 2) {
			g[r[i][1]].push_back({ r[i][0], i });
		}
	}
	bol.clear();
	bol.resize(n, vec<bool>(2, false));
	dist[p][0][0] = 0;
	dist[p][1][1] = 0;
	bol[p][0] = 1;
	For(i, n) {
		//0->mozes pouzit najdrahsieho
		dfs(i, -1, 0);
		if(i != p) dfs(i, g[i][0].ss, 0);
	}
	bol.clear();
	bol.resize(n, vec<bool>(2, false));
	bol[p][1] = 1;
	For(i, n) {
		if(i != p) dfs(i, -1, 1);
		dfs(i, g[i][0].ss, 1);
		if (g[i].size() == 1) {
			dist[i][1][0] = dist[i][0][0];
			dist[i][1][1] = dist[i][0][1];
		}
	}
	vec<pii> o;
	For(i, q) {
		o.push_back({ pq[i], i });
	}
	sort(o.begin(), o.end());
	vec<vec<ll>> pp(2);
	For(i, n) {
		For(j, 2) {
			if (dist[i][0][j] < 0) continue;
			pp[j].push_back(dist[i][0][j]);
		}
	}
	sort(pp[0].begin(), pp[0].end());
	sort(pp[1].begin(), pp[1].end());

	vec<ll> vys(q, 0);

	//vyries pripad ze vychadza iba 1 hrana
	//zaciatok divneho pripadu
	if (g[p].size() == 1) {
		ll jtyp = 0;
		if (g[g[p][0].ff][0].ss == g[p][0].ss) jtyp = 1;
		ll q1 = dist[g[p][0].ff][jtyp][0] + 1;
		ll som = 0;
		vec<ll> zv(q1 + 1, 0);
		For(i, o.size()) {
			while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
				zv[pp[0][som] % q1]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % q1];
		}
		For(i, q) {
			answer(vys[i]);
		}
		return;
	}

	//koniec divneho pripadu

	ll sit1 = 0;
	ll q11, q12;
	ll jtyp = 0;
	if (g[g[p][0].ff][0].ss == g[p][0].ss) jtyp = 1;
	q11 = dist[g[p][0].ff][jtyp][0] + 1;
	q12 = dist[g[p][0].ff][jtyp][1] + 1;
	ll q21, q22;
	jtyp = 0;
	pii dh = g[p][1];
	if (g[dh.ff][0].ss == dh.ss) jtyp = 1;
	q21 = dist[dh.ff][jtyp][0] + 1;
	q22 = dist[dh.ff][jtyp][1] + 1;



	//situacia 4
	if (q12 > 0 && q21 > 0) {
		ll q1 = q12;
		ll q2 = q21;
		ll som = 0;
		vec<ll> zv(q1 + q2 + 1, 0);

		som = 0;
		For(i, o.size()) {
			while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
				zv[pp[0][som] % (q1 + q2)]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % (q1 + q2)];
		}

		som = 0;
		zv.clear();
		zv.resize(q1 + q2 + 1, 0);
		For(i, o.size()) {
			while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
				zv[pp[1][som] % (q1 + q2)]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % (q1 + q2)];
		}
		For(i, q) {
			answer(vys[i]);
		}
		return;
	}








	//situacia 1
	
	if (q11 > 0 && q22 > 0) {
		ll q1 = q11;
		ll q2 = q22;
		ll som = 0;
		vec<ll> zv(q1 + 1, 0);
		For(i, o.size()) {
			while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
				zv[pp[0][som] % q1]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % q1];
		}
		som = 0;
		zv.clear();
		zv.resize(q2 + 1, 0);
		For(i, o.size()) {
			while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
				zv[pp[1][som] % q2]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % q2];
		}
		For(i, q) {
			answer(vys[i]);
		}
		return;
	}



	//situacia 2
	if (q12 > 0 && q22 > 0) {
		ll q1 = q12;
		ll q2 = q22;
		ll som = 0;
		vec<ll> zv(q2 + 1, 0);
		vec<ll> poc(3 * n, 0);
		For(i, pp[0].size()) {
			poc[pp[0][i]]++;
		}
		For(i, o.size()) {
			if (o[i].ff < poc.size()) vys[o[i].ss] += poc[o[i].ff];
		}
		som = 0;
		zv.clear();
		zv.resize(q2 + 1, 0);
		For(i, o.size()) {
			while (som < pp[1].size() && pp[1][som] <= o[i].ff) {
				zv[pp[1][som] % q2]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % q2];
		}
		For(i, q) {
			answer(vys[i]);
		}
		return;
	}



	//situacia 3
	if (q11 > 0 && q21 > 0) {
		ll q1 = q11;
		ll q2 = q21;
		ll som = 0;
		vec<ll> zv(q1 + 1, 0);
		For(i, o.size()) {
			while (som < pp[0].size() && pp[0][som] <= o[i].ff) {
				zv[pp[0][som] % q1]++;
				som++;
			}
			vys[o[i].ss] += zv[o[i].ff % q1];
		}
		som = 0;
		zv.clear();


		zv.resize(q2 + 1, 0);
		vec<ll> poc(3 * n, 0);
		For(i, pp[1].size()) {
			poc[pp[1][i]]++;
		}
		For(i, o.size()) {
			if(o[i].ff < poc.size()) vys[o[i].ss] += poc[o[i].ff];
		}
		For(i, q) {
			answer(vys[i]);
		}
		return;
	}
	return;
}

/*
int main() {
	while (true) {
		int n1, m1, p1, r1[1000][2], q1, g1[1000];
		//cin >> n1 >> m1 >> p1;
		n1 = rand() % 10 + 2;
		m1 = rand() % 10 + n1;
		p1 = rand() % n1;
		For(i, n1) {
			//cin >> r1[i][0] >> r1[i][1];
			r1[i][0] = i;
			r1[i][1] = rand() % n1;
		}
		For(i, m1 - n1) {
			while (true) {
				r1[i + n1][0] = rand() % n1;
				r1[i + n1][1] = rand() % n1;
				if (r1[i + n1][0] != r1[i + n1][1]) break;
			}
		}
		//cin >> q1;
		q1 = 1;
		For(i, q1) {
			//cin >> g1[i];
			g1[i] = rand() % 1000000000;
		}
		cout << n1 << ' ' << m1 << ' ' << p1 << '\n';
		For(i, m1) {
			cout << r1[i][0] << ' ' << r1[i][1] << '\n';
		}
		cout << q1 << '\n';
		For(i, q1) {
			cout << g1[i] << '\n';
		}
		count_routes(n1, m1, p1, r1, q1, g1);
	}
	return 0;
}*/

Compilation message (stderr)

garden.cpp: In function 'long long int dfs(long long int, long long int, long long int)':
garden.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31