oj.uz

Submission #960004

# Submission time Handle Problem Language Result Execution time Memory
960004 2024-04-09T12:37:28 Z pcc Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 198 ms 42816 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const int mxn = 5e5+10;

int N,M;
vector<int> paths[mxn];
int deg[mxn];
queue<int> q;
int ans[mxn];
bitset<mxn> done;
vector<int> v;
int col[mxn];
vector<int> bipart[2];

void dfs(int now,int c){
	col[now] = c;
	bipart[col[now]==1].push_back(now);
	for(auto nxt:paths[now]){
		if(done[nxt]||col[nxt])continue;
		dfs(nxt,-c);
	}
}

void psyco(int now){
	bipart[0].clear();bipart[1].clear();
	dfs(now,1);
	bool zcol = true,ocol = true;
	for(auto &i:bipart[0])if(!ans[i])zcol = false;
	for(auto &i:bipart[1])if(!ans[i])ocol = false;
	if(!ocol&&!zcol){
		cout<<-1;
		exit(0);
	}
	if(zcol)for(auto &i:bipart[0])v.push_back(i);
	else for(auto &i:bipart[1])v.push_back(i);
	for(auto &i:bipart[0])done[i] = true;
	for(auto &i:bipart[1])done[i] = true;
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	memset(ans,-1,sizeof(ans));
	for(int i = 1;i<=M;i++){
		int a,b;
		cin>>a>>b;
		deg[a]++;
		paths[b].push_back(a);
	}
	for(int i = 1;i<=N;i++)if(!deg[i])q.push(i);
	while(!q.empty()){
		auto now = q.front();
		done[now] = true;
		q.pop();
		if(ans[now] == -1)ans[now] = 1;
		for(auto nxt:paths[now]){
			deg[nxt]--;
			if(!deg[nxt])q.push(nxt);
			if(ans[now] == 1){
				if(ans[nxt] == -1)ans[nxt] = 0;
			}
		}
	}
	for(int i = 1;i<=N;i++){
		if(ans[i] == 1)v.push_back(i);
	}
	for(int i = 1;i<=N;i++){
		if(!done[i])psyco(i);
	}
	cout<<v.size()<<'\n';
	for(auto &i:v)cout<<i<<' ';cout<<'\n';
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:81:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   81 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |  ^~~
Main.cpp:81:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |  for(auto &i:v)cout<<i<<' ';cout<<'\n';
      |                             ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 40652 KB Output is correct
2 Correct 105 ms 40492 KB Output is correct
3 Correct 4 ms 17756 KB Output is correct
4 Correct 36 ms 25020 KB Output is correct
5 Correct 63 ms 32076 KB Output is correct
6 Correct 103 ms 42572 KB Output is correct
7 Correct 59 ms 25288 KB Output is correct
8 Correct 116 ms 35456 KB Output is correct
9 Correct 165 ms 33988 KB Output is correct
10 Correct 131 ms 40520 KB Output is correct
11 Correct 160 ms 36936 KB Output is correct
12 Correct 198 ms 34384 KB Output is correct
13 Correct 141 ms 35152 KB Output is correct
14 Correct 144 ms 35084 KB Output is correct
15 Correct 129 ms 35148 KB Output is correct
16 Correct 123 ms 35068 KB Output is correct
17 Correct 32 ms 21332 KB Output is correct
18 Correct 64 ms 23636 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 40652 KB Output is correct
2 Correct 100 ms 42816 KB Output is correct
3 Correct 54 ms 25036 KB Output is correct
4 Correct 167 ms 36168 KB Output is correct
5 Incorrect 194 ms 36064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18008 KB Output is correct
2 Correct 5 ms 18008 KB Output is correct
3 Correct 4 ms 18008 KB Output is correct
4 Correct 5 ms 18012 KB Output is correct
5 Incorrect 6 ms 18008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 40652 KB Output is correct
2 Correct 105 ms 40492 KB Output is correct
3 Correct 4 ms 17756 KB Output is correct
4 Correct 36 ms 25020 KB Output is correct
5 Correct 63 ms 32076 KB Output is correct
6 Correct 103 ms 42572 KB Output is correct
7 Correct 59 ms 25288 KB Output is correct
8 Correct 116 ms 35456 KB Output is correct
9 Correct 165 ms 33988 KB Output is correct
10 Correct 131 ms 40520 KB Output is correct
11 Correct 160 ms 36936 KB Output is correct
12 Correct 198 ms 34384 KB Output is correct
13 Correct 141 ms 35152 KB Output is correct
14 Correct 144 ms 35084 KB Output is correct
15 Correct 129 ms 35148 KB Output is correct
16 Correct 123 ms 35068 KB Output is correct
17 Correct 32 ms 21332 KB Output is correct
18 Correct 64 ms 23636 KB Output is correct
19 Correct 101 ms 40652 KB Output is correct
20 Correct 100 ms 42816 KB Output is correct
21 Correct 54 ms 25036 KB Output is correct
22 Correct 167 ms 36168 KB Output is correct
23 Incorrect 194 ms 36064 KB Output isn't correct
24 Halted 0 ms 0 KB -