Submission #425115

#	Time	Username	Problem	Language	Result	Execution time	Memory
425115		keta_tsimakuridze	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2097 ms	212928 KiB

bitaro

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int fix[N],in[N],x[N],n,m,Q,mx[N],Sq,a[N];
vector<pair<int,int> > c[N];
vector<int>V[N],t;
queue<int>q;
void merge(int a,int b){
	vector<pair<int,int> > v;
	int i = -1, j = -1;
	while(v.size() < Sq && (i + 1 < c[a].size() || j + 1<c[b].size()) ) {
		if(i+1==c[a].size()) {
			j++;
			if(!fix[c[b][j].s]) v.push_back({c[b][j].f+1,c[b][j].s});
			fix[c[b][j].s] = 1;
			t.push_back(c[b][j].s);	
			continue;
		}
		if(j+1==c[b].size()){
			i++;
			if(!fix[c[a][i].s]) v.push_back(c[a][i]);
			fix[c[a][i].s] = 1;
			t.push_back(c[a][i].s);
			continue;
		}
		if(c[a][i+1].f < c[b][j+1].f+1) {
			j++;
			if(!fix[c[b][j].s]) v.push_back({c[b][j].f+1,c[b][j].s});
			fix[c[b][j].s] = 1;	
			t.push_back(c[b][j].s);	
		} 
		else {
			i++;
			if(!fix[c[a][i].s]) v.push_back(c[a][i]);
			fix[c[a][i].s] = 1;
			t.push_back(c[a][i].s);
		}
		
	}
	c[a] = v;
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>Q;
	Sq = 250;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		if(u > v) swap(u,v);
		V[u].push_back(v);
		in[v]++;
		x[v]++;
	}
	for(int i=1;i<=n;i++){
		if(!in[i]) q.push(i);
	}
	while(q.size()){
		int u = q.front(); 
		if(c[u].size() < Sq) {
			c[u].push_back({0,u});
		}
		q.pop();
		for(int i=0;i<V[u].size();i++) {
			in[V[u][i]]--;
			t.clear();
			merge(V[u][i],u);
			
			for(int j=0;j<t.size();j++) fix[t[j]] = 0;
			if(!in[V[u][i]]) q.push(V[u][i]);
		}
	}
	while(Q--){
		int u, k;
		cin >> u >> k;
		for(int i=1;i<=k;i++)  {
			cin >> a[i]; fix[a[i]] = 1;
		} 
		if(k <= Sq-1) { 
			int ans = 0;
			for(int i=0;i<c[u].size();i++) {
				if(fix[c[u][i].s]) continue;
				ans = c[u][i].f; break;
			}
			if(!ans && fix[u]){
				cout<<-1<<" ";
			}
			else cout<<ans<<" ";
		}
		else  {
			for(int i=1;i<=n;i++) {
				in[i] = x[i]; mx[i] = -1;
				if(!in[i]) q.push(i);
			} 
			while(q.size()){
				int u = q.front();
				q.pop();
				//if(mx[u]==-1 && fix[u]) continue;
				if(!fix[u]) mx[u] = max(mx[u],0);
				for(int i=0;i<V[u].size();i++){
					in[V[u][i]]--;
				    if(mx[u]!=-1) mx[V[u][i]] = max(mx[V[u][i]],mx[u] + 1);
					if(!in[V[u][i]] ) q.push(V[u][i]);
				}
			}
			cout<<mx[u]<<" ";
		}
		for(int i=1;i<=k;i++) fix[a[i]] = 0;
	}

}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int, int)':
bitaro.cpp:13:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |  while(v.size() < Sq && (i + 1 < c[a].size() || j + 1<c[b].size()) ) {
      |        ~~~~~~~~~^~~~
bitaro.cpp:13: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]
   13 |  while(v.size() < Sq && (i + 1 < c[a].size() || j + 1<c[b].size()) ) {
      |                          ~~~~~~^~~~~~~~~~~~~
bitaro.cpp:13:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  while(v.size() < Sq && (i + 1 < c[a].size() || j + 1<c[b].size()) ) {
      |                                                 ~~~~~^~~~~~~~~~~~
bitaro.cpp:14:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   if(i+1==c[a].size()) {
      |      ~~~^~~~~~~~~~~~~
bitaro.cpp:21:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if(j+1==c[b].size()){
      |      ~~~^~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:61: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]
   61 |   if(c[u].size() < Sq) {
      |      ~~~~~~~~~~~~^~~~
bitaro.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<V[u].size();i++) {
      |               ~^~~~~~~~~~~~
bitaro.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for(int j=0;j<t.size();j++) fix[t[j]] = 0;
      |                ~^~~~~~~~~
bitaro.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for(int i=0;i<c[u].size();i++) {
      |                ~^~~~~~~~~~~~
bitaro.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<V[u].size();i++){
      |                 ~^~~~~~~~~~~~

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