Submission #425087

#	Time	Username	Problem	Language	Result	Execution time	Memory
425087		keta_tsimakuridze	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2079 ms	11912 KiB

bitaro

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,fix[N],in[N],x[N],n,m,Q,mx[N],Sq;
vector<pair<int,int> > c[N];
vector<int>V[N];
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;
			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;
			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;		
		} 
		else {
			i++;
			if(!fix[c[a][i].s]) v.push_back(c[a][i]);
			fix[c[a][i].s] = 1;
		}
		
	}
	c[a] = v;
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>Q;
	Sq = sqrt(n);
	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]]--;
			merge(V[u][i],u);
			memset(fix,0,sizeof(fix));
			if(!in[V[u][i]]) q.push(V[u][i]);
		}
	}
	while(Q--){
		int u, k;
		cin >> u >> k;
		memset(fix,0,sizeof(fix));
		for(int i=1;i<=k;i++)  {
			int a;
			cin >> a; fix[a] = 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]<<" ";
		}
	}

}

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:20: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]
   20 |   if(j+1==c[b].size()){
      |      ~~~^~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:57: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]
   57 |   if(c[u].size() < Sq) {
      |      ~~~~~~~~~~~~^~~~
bitaro.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=0;i<V[u].size();i++) {
      |               ~^~~~~~~~~~~~
bitaro.cpp:78: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]
   78 |    for(int i=0;i<c[u].size();i++) {
      |                ~^~~~~~~~~~~~
bitaro.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<V[u].size();i++){
      |                 ~^~~~~~~~~~~~

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