oj.uz

Submission #881049

# Submission time Handle Problem Language Result Execution time Memory
881049 2023-11-30T12:09:30 Z epicci23 Povjerenstvo (COI22_povjerenstvo) C++17
21 / 100
 317 ms 64988 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 * SIMPLIFY THE PROBLEM
 * READ THE STATEMENT CAREFULLY
  !!! if there is an specified/interesting smth(i.e. constraint) in the statement,
  then you must be careful about that   
*/

const int N = 5e5 + 5;
vector<int> v[N],cur[2],vis(N,0);

void dfs(int c,int col){
  cur[col].pb(c);
  vis[c]=1;
  for(int x:v[c]){
    if(vis[x]) continue;
    dfs(x,!col);
  }  
}

void solve(){
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		int a,b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
	}
   
    vector<int> ans;

    for(int i=1;i<=n;i++){
      if(vis[i]) continue;
      cur[0].clear();cur[1].clear();
      dfs(i,0);
      if(sz(cur[0])<sz(cur[1])) swap(cur[0],cur[1]);
      for(int x:cur[0]) ans.pb(x); 
    }

    cout << sz(ans) << endl;
    for(int x:ans) cout << x << " ";
    cout << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 64356 KB Output is correct
2 Correct 109 ms 43528 KB Output is correct
3 Correct 4 ms 15960 KB Output is correct
4 Correct 36 ms 22980 KB Output is correct
5 Correct 71 ms 38720 KB Output is correct
6 Correct 104 ms 48568 KB Output is correct
7 Correct 107 ms 51004 KB Output is correct
8 Correct 101 ms 48704 KB Output is correct
9 Correct 224 ms 48332 KB Output is correct
10 Correct 210 ms 45696 KB Output is correct
11 Correct 222 ms 48064 KB Output is correct
12 Incorrect 317 ms 52956 KB There must not be two people within the committee such that one person dislikes the other.
13 Halted 0 ms 0 KB -

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 64476 KB Output is correct
2 Correct 103 ms 49872 KB Output is correct
3 Correct 105 ms 49984 KB Output is correct
4 Correct 236 ms 47452 KB Output is correct
5 Correct 309 ms 54756 KB Output is correct
6 Correct 174 ms 44224 KB Output is correct
7 Correct 163 ms 43968 KB Output is correct
8 Correct 145 ms 43376 KB Output is correct
9 Correct 135 ms 44140 KB Output is correct
10 Correct 43 ms 23376 KB Output is correct
11 Correct 51 ms 21332 KB Output is correct
12 Correct 39 ms 21552 KB Output is correct
13 Correct 132 ms 64988 KB Output is correct
14 Correct 139 ms 44228 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16476 KB Output is correct
2 Correct 7 ms 16476 KB Output is correct
3 Correct 5 ms 16476 KB Output is correct
4 Correct 5 ms 16220 KB Output is correct
5 Correct 6 ms 16220 KB Output is correct
6 Correct 5 ms 16220 KB Output is correct
7 Correct 6 ms 16220 KB Output is correct
8 Correct 6 ms 16220 KB Output is correct
9 Correct 5 ms 15964 KB Output is correct
10 Correct 4 ms 15964 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 5 ms 16476 KB Output is correct
13 Correct 5 ms 16220 KB Output is correct
14 Incorrect 4 ms 15964 KB There must not be two people within the committee such that one person dislikes the other.
15 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 64356 KB Output is correct
2 Correct 109 ms 43528 KB Output is correct
3 Correct 4 ms 15960 KB Output is correct
4 Correct 36 ms 22980 KB Output is correct
5 Correct 71 ms 38720 KB Output is correct
6 Correct 104 ms 48568 KB Output is correct
7 Correct 107 ms 51004 KB Output is correct
8 Correct 101 ms 48704 KB Output is correct
9 Correct 224 ms 48332 KB Output is correct
10 Correct 210 ms 45696 KB Output is correct
11 Correct 222 ms 48064 KB Output is correct
12 Incorrect 317 ms 52956 KB There must not be two people within the committee such that one person dislikes the other.
13 Halted 0 ms 0 KB -