Submission #900585

#	Time	Username	Problem	Language	Result	Execution time	Memory
900585		falaz	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	40 ms	8536 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

bitaro

#include <bits/stdc++.h> 
using namespace std;

#pragma GCC optimize ("O2,unroll-loops, Ofast")
#pragma GCC optimize ("O2,unroll-loops, Ofast")
#pragma GCC optimize ("Ofast")
#pragma gcc optimize("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")

#define endl '\n'
//#define int long long

#define F first 
#define S second

const int N = 1e5 + 3, SQ = 400;
int n, m, q, dis[N];
vector<int> radj[N];
queue<int> qu;
bool mark[N];
vector<pair<int, int>> vec[N];

void bfs() {
	while(qu.size()) {
		int v = qu.front();
		mark[v] = false;
		qu.pop();
		for (auto u : radj[v]) 
			if (dis[v] + 1 > dis[u]) {
				dis[u] = dis[v] + 1;
				if (!mark[u]) {
					qu.push(u);
					mark[u] = true;
				}
			}
	}
}

signed main(){
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		radj[u].push_back(v);
	}
	set<pair<int, int>> st;
	for (int i = 1; i <= n; i++) { 
		if (radj[i].size() == 0)
			vec[i].push_back({i, 0});
		else {
			for (auto v : radj[i]) {
				for (auto u : vec[v]) {
					if (dis[u.F] == 0) {
						dis[u.F] = u.S + 1;
						st.insert({dis[u.F], u.F});
					}
					else if(dis[u.F] < u.S + 1) {
						st.erase({dis[u.F], u.F});
						dis[u.F] = u.S + 1;
						st.insert({dis[u.F], u.F});
					}
					if (st.size() > SQ) {
						int f = st.begin()->S;
						dis[f] = 0;
						st.erase(st.begin());
					}
				}
			}
			while (st.size()) {
				int v = st.begin()->second, f = st.begin()->first;
				st.erase(st.begin());
				vec[i].push_back({v, f});
				dis[v] = 0;
			}
			vec[i].push_back({i, 0});
			sort(vec[i].begin(), vec[i].end());
		}
	}
	while (q--) {
		int t, y;
		cin >> t >> y;
		int c[y + 1];
		c[y] = n + 1;
		for (int i = 0; i < y; i++)
			cin >> c[i];
		if (y < SQ) {
			int p = 0, ans = -1;
			for (int i = 0; i < int32_t(vec[t].size()); i++) {
				while (c[p] < vec[t][i].F)
					p++;
				if (vec[t][i].F != c[p]) 
					ans = max(vec[t][i].S, ans);
			}
			cout << ans << endl;
		}
		else {
			qu.push(t);
			bfs();
			int p = 0, ans = -1;
			for (int i = 1; i <= t; i++) {
				while (c[p] < i)
					p++;
				if (i != c[p]) 
					ans = max(ans, dis[i]);
				dis[i] = 0;
			}
			cout << ans << endl;
		}
	}	
}

Compilation message (stderr)

bitaro.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
bitaro.cpp:8: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    8 | #pragma optimize(Ofast)
      | 
bitaro.cpp:4:47: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize ("O2,unroll-loops, Ofast")
      |                                               ^
bitaro.cpp:5:47: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
    5 | #pragma GCC optimize ("O2,unroll-loops, Ofast")
      |                                               ^
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   11 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")
      |                                                                              ^
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
bitaro.cpp:11:78: warning: bad option '-f Ofast' to attri

Subtask 10 / 7

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 20 / 7

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 30 / 86

#	Verdict	Execution time	Memory	Grader output
Fetching results...