Submission #290400

#	Time	Username	Problem	Language	Result	Execution time	Memory
290400		Autoratch	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	5 ms	7424 KiB

bitaro

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

const int N = 1e5 + 1;
const int K = 450;

int n,m,k;
vector<int> adj[N],rev[N];
int deg[N],id[N];
queue<int> q;
vector<pair<int,int> > res[N];
bool out[N];
stack<int> st;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m >> k;
	for(int i = 0;i < m;i++)
	{
		int a,b;
		cin >> a >> b;
		deg[b]++;
		adj[a].push_back(b);
		rev[b].push_back(a);
	}
	for(int i = 1;i <= n;i++) if(!deg[i]) q.push(i);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int v : rev[u]) id[v] = 0;
		for(int j = 0;j < K;j++)
		{
			pair<int,int> mx = {u,0};
			for(int v : rev[u]) 
			{
				while(id[v]<res[v].size() and out[res[v][id[v]].first]) id[v]++;
				if(id[v]<res[v].size() and res[v][id[v]].second+1>mx.second) mx = {res[v][id[v]].first,res[v][id[v]].second+1};
			}
			res[u].push_back(mx);
			out[mx.first] = true;
			st.push(mx.first);
			if(mx.first==u) break;
			else id[mx.first]++;
		}
		while(!st.empty()) out[st.top()] = false,st.pop();
		for(int v : adj[u]) 
		{
			deg[v]--;
			if(deg[v]==0) q.push(v);
		}
	}
	for(int i = 1;i <= n;i++)
	{
		for(int j = 0;j < res[i].size()-1;j++) assert(res[i][j].second>=res[i][j+1].second);
	}
	while(k--)
	{
		int u,am;
		cin >> u >> am;
		while(am--){ int x; cin >> x; out[x] = true; st.push(x); }
		if(am>=K)
		{

		}
		else
		{
			for(auto [x,y] : res[u]) if(!out[x]){ cout << y << '\n'; break; } 
		}
		while(!st.empty()) out[st.top()] = false,st.pop();
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(id[v]<res[v].size() and out[res[v][id[v]].first]) id[v]++;
      |           ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(id[v]<res[v].size() and res[v][id[v]].second+1>mx.second) mx = {res[v][id[v]].first,res[v][id[v]].second+1};
      |        ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = 0;j < res[i].size()-1;j++) assert(res[i][j].second>=res[i][j+1].second);
      |                 ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:70:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |    for(auto [x,y] : res[u]) if(!out[x]){ cout << y << '\n'; break; }
      |             ^

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