Submission #1231019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231019		salmon	Povjerenstvo (COI22_povjerenstvo)	C++20	100 / 100	419 ms	97616 KiB

Main

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

int N;
int M;
int u,v;
int parent[500100];
vector<int> adjlst[500100];
vector<int> badjlst[500100];
int d[500100];
bool used[500100];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
bool visited[500100];
vector<int> order;
int it = 0;

void dfs(int i){
	visited[i] = true;
	
	for(int j : adjlst[i]) if(!visited[j]) dfs(j);
	
	order.push_back(i);
}

int main(){

	scanf(" %d",&N);
	scanf(" %d",&M);
	
	for(int i = 0; i < M; i++){
		scanf(" %d",&u);
		scanf(" %d",&v);
		
		adjlst[u].push_back(v);
		badjlst[v].push_back(u);
		
		d[u]++;
	}
	
	for(int i = 1; i <= N; i++){
		parent[i] = 1;
		used[i] = false;
		pq.push({d[i],i});
	}
	
	for(int i = 1; i <= N; i++) if(!visited[i]) dfs(i);
	
	vector<int> bosen;
	
	int cont = 0;
	
	while(cont != N){
		if(used[pq.top().second]){
			pq.pop();
			continue;
		}
		cont++;
		
		if(pq.top().first == 0){
			int i = pq.top().second;
			pq.pop();
			
			used[i] = true;
			
			bosen.push_back(i);
			
			for(int j : badjlst[i]){
				if(!used[j]){
					used[j] = true;
					cont++;
					for(int k : badjlst[j]){
						d[k]--;
						pq.push({d[k],k});
					}
				}
			}
			
			for(int j : adjlst[i]){
				if(!used[j]){
					used[j] = true;
					cont++;
					for(int k : badjlst[j]){
						d[k]--;
						pq.push({d[k],k});
					}
				}
			}
		}
		else{
			while(used[order[it]]){
				it++;
			}
			
			int i = order[it];
			
			used[i] = true;
			
			bosen.push_back(i);
			
			for(int j : badjlst[i]){
				if(!used[j]){
					used[j] = true;
					cont++;
					for(int k : badjlst[j]){
						d[k]--;
						pq.push({d[k],k});
					}
				}
			}
			
			for(int j : adjlst[i]){
				if(!used[j]){
					used[j] = true;
					cont++;
					for(int k : badjlst[j]){
						d[k]--;
						pq.push({d[k],k});
					}
				}
			}
			
			it++;
		}
	}
	
	printf("%d\n",bosen.size());
	for(int i : bosen) printf("%d ",i);
	printf("\n");
	
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:126:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  126 |         printf("%d\n",bosen.size());
      |                 ~^    ~~~~~~~~~~~~
      |                  |              |
      |                  int            std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
Main.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
Main.cpp:31:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
Main.cpp:32:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33