Submission #860568

#	Time	Username	Problem	Language	Result	Execution time	Memory
860568		phoenix0423	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1025 ms	421148 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e9;
vector<int> adj[maxn], radj[maxn];
int n, m, q, sn;
vector<pll> p[maxn];
int used[maxn], bad[maxn];
int dist[maxn];

void init(){
	for(int i = 0; i < n; i++){
		for(auto x : radj[i]){
			vector<pll> nw;
			int l1 = 0, l2 = 0;
			while(nw.size() < sn){
				while(l1 < p[i].size() && used[p[i][l1].s]) l1++;
				while(l2 < p[x].size() && used[p[x][l2].s]) l2++;
				if(l1 == p[i].size() && l2 == p[x].size()) break;
				if(l1 == p[i].size()) used[p[x][l2].s] = 1, nw.pb(p[x][l2++]);
				else if(l2 == p[x].size()) used[p[i][l1].s] = 1, nw.pb(p[i][l1++]);
				else if(p[i][l1].f >= p[x][l2].f) used[p[i][l1].s] = 1, nw.pb(p[i][l1++]);
				else used[p[x][l2].s] = 1, nw.pb(p[x][l2++]);
			}
			swap(p[i], nw);
			for(auto [val, id] : p[i]) used[id] = 0;
		}
		for(int j = 0; j < p[i].size(); j++) p[i][j].f ++;
		if(p[i].size() < sn) p[i].pb({0, i});
	}
}

int find_max_path(int tar){
	for(int i = 0; i < n; i++) dist[i] = -INF;
	dist[tar] = 0;
	int ans = -1;
	for(int i = tar; i >= 0; i--){
		for(auto x : adj[i]) dist[i] = max(dist[i], dist[x] + 1);
		if(!bad[i]) ans = max(ans, dist[i]);
	}
	return ans;
}

int main(void){
	fastio;
	cin>>n>>m>>q;
	sn = sqrt(n);
	for(int i = 0; i < m; i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		adj[a].pb(b);
		radj[b].pb(a);
	}
	init();
	for(int i = 0; i < q; i++){
		int t, y;
		cin>>t>>y;
		t--;
		vector<int> ng(y);
		for(int j = 0; j < y; j++){
			cin>>ng[j];
			ng[j] --;
			bad[ng[j]] = 1;
		}
		if(y >= sn){
			cout<<find_max_path(t)<<"\n";
		}
		else{
			int ans = -1;
			for(auto [val, id] : p[t]){
				if(!bad[id]){
					ans = val;
					break;
				}
			}
			cout<<ans<<"\n";
		}
		for(auto x : ng) bad[x] = 0;
	}

}

Compilation message (stderr)

bitaro.cpp: In function 'void init()':
bitaro.cpp:24:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |    while(nw.size() < sn){
      |          ~~~~~~~~~~^~~~
bitaro.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while(l1 < p[i].size() && used[p[i][l1].s]) l1++;
      |           ~~~^~~~~~~~~~~~~
bitaro.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(l2 < p[x].size() && used[p[x][l2].s]) l2++;
      |           ~~~^~~~~~~~~~~~~
bitaro.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(l1 == p[i].size() && l2 == p[x].size()) break;
      |        ~~~^~~~~~~~~~~~~~
bitaro.cpp:27:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(l1 == p[i].size() && l2 == p[x].size()) break;
      |                             ~~~^~~~~~~~~~~~~~
bitaro.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(l1 == p[i].size()) used[p[x][l2].s] = 1, nw.pb(p[x][l2++]);
      |        ~~~^~~~~~~~~~~~~~
bitaro.cpp:29: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]
   29 |     else if(l2 == p[x].size()) used[p[i][l1].s] = 1, nw.pb(p[i][l1++]);
      |             ~~~^~~~~~~~~~~~~~
bitaro.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int j = 0; j < p[i].size(); j++) p[i][j].f ++;
      |                  ~~^~~~~~~~~~~~~
bitaro.cpp:37:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if(p[i].size() < sn) p[i].pb({0, i});
      |      ~~~~~~~~~~~~^~~~

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