Submission #1146570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146570		sano	Tropical Garden (IOI11_garden)	C++20	49 / 100	89 ms	40348 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(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 1000000000
#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<int>>> dist;
/*
void answer(int x) {
	cout << x << '\n';
	return;
}
*/

int dfs(int x, vec<vec<bool>>&bol, int pr, int 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, bol, 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<int>>(2, vec<int>(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 });
		}
	}
	vec<vec<bool>> bol(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, bol, -1, 0);
		if(i != p) dfs(i, bol, 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, bol, -1, 1);
		dfs(i, bol, 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<int>> 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<int> vys(q, 0);

	//vyries pripad ze vychadza iba 1 hrana
	//zaciatok divneho pripadu
	if (g[p].size() == 1) {
		int jtyp = 0;
		if (g[g[p][0].ff][0].ss == g[p][0].ss) jtyp = 1;
		int q1 = dist[g[p][0].ff][jtyp][0] + 1;
		int som = 0;
		vec<int> 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

	int sit1 = 0;
	int q11, q12;
	int 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;
	int 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) {
		int q1 = q12;
		int q2 = q21;
		int som = 0;
		vec<int> 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) {
		int q1 = q11;
		int q2 = q22;
		int som = 0;
		vec<int> 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) {
		int q1 = q12;
		int q2 = q22;
		int som = 0;
		vec<int> zv(q2 + 1, 0);
		vec<int> poc(2 * n, 0);
		For(i, pp[0].size()) {
			poc[pp[0][i]]++;
		}
		For(i, o.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) {
		int q1 = q11;
		int q2 = q22;
		int som = 0;
		vec<int> 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<int> poc(2 * n, 0);
		For(i, pp[1].size()) {
			poc[pp[1][i]]++;
		}
		For(i, o.size()) {
			vys[o[i].ss] += poc[o[i].ff];
		}
		For(i, q) {
			answer(vys[i]);
		}
		return;
	}
	return;
}


/*int main() {
	int n1, m1, p1, r1[1000][2], q1, g1[1000];
	//cin >> n1 >> m1 >> p1;
	n1 = 1000;
	m1 = n1 - 1;
	p1 = 0;
	For(i, m1) {
		//cin >> r1[i][0] >> r1[i][1];
		r1[i][0] = i;
		r1[i][1] = i + 1;
	}
	//cin >> q1;
	q1 = 1;
	For(i, q1) {
		//cin >> g1[i];
		g1[i] = 100;
	}
	count_routes(n1, m1, p1, r1, q1, g1);
	return 0;
}*/

Compilation message (stderr)

garden.cpp: In function 'int dfs(int, std::vector<std::vector<bool> >&, int, int)':
garden.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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