Submission #923103

#	Time	Username	Problem	Language	Result	Execution time	Memory
923103		NintsiChkhaidze	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1106 ms	433820 KiB

bitaro

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,
using namespace std;

const int N = 2e5 + 3;

int b[N],id,vis[N],fix[N],dp[N],f[N];
vector <int> g[N],v[N],ord;
vector <pii> paths[N];

void topsort(int x){
	vis[x]=1;
	for (int to: v[x])
		if (!vis[to]) topsort(to);
	ord.pb(x);
}

vector <pii> merge(vector <pii> x,vector <pii> y){
	for (int i = 0; i < x.size(); i++)
		x[i].f += 1;
		
	++id;
	int l1 = 0,l2 = 0;
	vector <pii> vec;
	while (l1 < x.size() || l2 < y.size()){
		while (l1 < x.size() && fix[x[l1].s] == id) l1++;
		while (l2 < y.size() && fix[y[l2].s] == id) l2++;
		
		if (l1 == x.size()) {
			vec.pb(y[l2]);
			fix[y[l2].s] = id;
			++l2;
			continue;
		}
		
		if (l2 == y.size()){
			vec.pb(x[l1]);
			fix[x[l1].s] = id;
			++l1;
			continue;
		}
		
		if (x[l1] > y[l2]) {
			vec.pb(x[l1]);
			fix[x[l1].s] = id;
			++l1;
			continue;
		}
		
		vec.pb(y[l2]);
		fix[y[l2].s] = id;
		++l2;
	}
	
	return vec;
}
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

    int n,m,q;
    cin>>n>>m>>q;
   
    for (int i = 1; i <= m; i++){
		int a,b;
		cin>>a>>b;
		g[b].pb(a);
		v[a].pb(b);
    }
    
    for (int i = 1; i <= n; i++){
    	if (!vis[i]) topsort(i);
 	}
 	reverse(ord.begin(),ord.end());
 	
 	int Bl = 320;
 	for (int x: ord){
		vector <pii> cur;
		cur.pb({0,x});
		for (int prev: g[x]){
			cur = merge(paths[prev], cur);
		}	
		
		for (int i = 0; i < cur.size(); i++){
			if (paths[x].size() == Bl) break;
			paths[x].pb(cur[i]); 
		}
	}
	
    while (q--){
    	int T,k;
    	cin>>T>>k;
    	for (int i = 1; i <= k; i++){
    		int x;
    		cin>>x;
    		b[i] = x;
    		f[x] = 1;
		}
			
		if (k < Bl){
			int ans = -1;
			for (auto [l,r]: paths[T]){
				if (!f[r]) {ans = l; break;}
			}
			cout<<ans<<endl;
		}else{
			for (int i = 1; i <= n; i++){
				if (f[i]) dp[i] = -1e9;
				else dp[i] = 0;
			}
			
			for (int x: ord){
				for (int prev: g[x]){
					dp[x] = max(dp[x],dp[prev] + 1);
				}
			}
			if (dp[T] < 0) cout<<-1<<endl;
			else cout<<dp[T]<<endl;
		}
		for (int i = 1; i <= k; i++)
			f[b[i]] = 0;
	}
	
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:25: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]
   25 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~
bitaro.cpp:31:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  while (l1 < x.size() || l2 < y.size()){
      |         ~~~^~~~~~~~~~
bitaro.cpp:31:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  while (l1 < x.size() || l2 < y.size()){
      |                          ~~~^~~~~~~~~~
bitaro.cpp:32: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]
   32 |   while (l1 < x.size() && fix[x[l1].s] == id) l1++;
      |          ~~~^~~~~~~~~~
bitaro.cpp:33: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]
   33 |   while (l2 < y.size() && fix[y[l2].s] == id) l2++;
      |          ~~~^~~~~~~~~~
bitaro.cpp:35:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (l1 == x.size()) {
      |       ~~~^~~~~~~~~~~
bitaro.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (l2 == y.size()){
      |       ~~~^~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = 0; i < cur.size(); i++){
      |                   ~~^~~~~~~~~~~~
bitaro.cpp:90:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |    if (paths[x].size() == Bl) break;
      |        ~~~~~~~~~~~~~~~~^~~~~

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