Submission #540723

#	Time	Username	Problem	Language	Result	Execution time	Memory
540723		GioChkhaidze	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1395 ms	272900 KiB

bitaro

#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 1e5 + 5;

bool f[N];
int n, m, q, d[N], ans[N];
vector < int > s[N], v[N], Q[N];
vector < pair < int , int > > rec[N];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		v[b].pb(a);
	}
	
	int sq = sqrt(n);
	for (int i = 1; i <= q; ++i) {
		int st, k;
		cin >> st >> k;
		for (int j = 1; j <= k; ++j) {
			int x;
			cin >> x;
			s[i].pb(x);
		}
		
		if (k >= sq) {
			for (int j = 0; j < s[i].size(); ++j) {
				f[s[i][j]] = true;
			}
			
			d[st] = 1;
			ans[i] = -1;
			for (int j = st; j >= 1; --j) {
				if (d[j]) {
					if (!f[j]) {
						ans[i] = max(ans[i], d[j] - 1);
					}
					for (int j2 = 0; j2 < v[j].size(); ++j2) {
						int to = v[j][j2];
						d[to] = max(d[j] + 1, d[to]);
					}
				}
			}

			for (int j = st; j >= 1; --j) d[j] = 0;
			for (int j = 0; j < s[i].size(); ++j) {
				f[s[i][j]] = false;
			}
		}
			else {
			Q[st].pb(i);	
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		rec[i].pb({0, i});
		for (int j = 0; j < v[i].size(); ++j) {
			int to = v[i][j];
			vector < pair < int , int > > ret;
			int isz = rec[i].size(), tosz = rec[to].size();
			int iid = 0, toid = 0, sz = min(sq + 5, isz + tosz);
			while (ret.size() < sz && (toid < tosz || iid < isz)) {
				if (toid < tosz && (iid == isz || rec[i][iid].f <= rec[to][toid].f + 1)) {
					if (!f[rec[to][toid].s]) {
						ret.pb({rec[to][toid].f + 1, rec[to][toid].s});
						f[rec[to][toid].s] = true;
					}
					++toid;
				}
					else
				if (iid < isz && (toid == tosz || rec[to][toid].f + 1 <= rec[i][iid].f)) {
					if (!f[rec[i][iid].s]) {
						f[rec[i][iid].s] = true;
						ret.pb(rec[i][iid]);
					}
				 	++iid;
				}
			}
			
			for (int k = 0; k < ret.size(); ++k) {
				f[ret[k].s] = false;
			}
			rec[i] = ret;
			ret.clear();	
		}

		for (int j = 0; j < Q[i].size(); ++j) {
			int id = Q[i][j];
			for (int k = 0; k < s[id].size(); ++k) {
				int x = s[id][k];
				f[x] = true;
			}	
			
			ans[id] = -1;
			for (int k = 0; k < rec[i].size(); ++k) {
				int x = rec[i][k].f, idx = rec[i][k].s;
				if (!f[idx]) {
					ans[id] = max(ans[id], x);
				}
			}
		
			for (int k = 0; k < s[id].size(); ++k) {
				int x = s[id][k];
				f[x] = false;
			}
		}
	}
	
	for (int i = 1; i <= q; ++i) {
		cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

bitaro.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main () {
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for (int j = 0; j < s[i].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~
bitaro.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |      for (int j2 = 0; j2 < v[j].size(); ++j2) {
      |                       ~~~^~~~~~~~~~~~~
bitaro.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int j = 0; j < s[i].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~
bitaro.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int j = 0; j < v[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~
bitaro.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |    while (ret.size() < sz && (toid < tosz || iid < isz)) {
      |           ~~~~~~~~~~~^~~~
bitaro.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for (int k = 0; k < ret.size(); ++k) {
      |                    ~~^~~~~~~~~~~~
bitaro.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int j = 0; j < Q[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~
bitaro.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for (int k = 0; k < s[id].size(); ++k) {
      |                    ~~^~~~~~~~~~~~~~
bitaro.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (int k = 0; k < rec[i].size(); ++k) {
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    for (int k = 0; k < s[id].size(); ++k) {
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86