oj.uz

Submission #863925

# Submission time Handle Problem Language Result Execution time Memory
863925 2023-10-21T13:05:49 Z Unforgettablepl Povjerenstvo (COI22_povjerenstvo) C++17
21 / 100
 302 ms 46680 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
ID: samikgo1
TASK: wormhole
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = 1e9;
const ll modulo = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#define int ll

vector<int> adj[500001];
bool visited[500001];
bool colour[500001];
int c;

void dfs(int x, bool col){
    if(visited[x] and colour[x]!=col){
        cout<<"-1\n";exit(0);
    }
    if(visited[x])return;
    if(col)c++;
    colour[x]=col;
    visited[x]=true;
    for(int&i:adj[x])dfs(i,!col);
}

void solve(){
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1,true);
    for(int i=1;i<=n;i++)if(!visited[i])dfs(i,true);
    cout << c << '\n';
    for(int i=1;i<=n;i++)if(colour[i])cout<<i<<' ';
    cout << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    int t;
//    cin >> t;
//    while(t--)
    solve();
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 46604 KB Output is correct
2 Correct 113 ms 36944 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 31 ms 16288 KB Output is correct
5 Correct 68 ms 33620 KB Output is correct
6 Correct 73 ms 34980 KB Output is correct
7 Correct 77 ms 36676 KB Output is correct
8 Correct 74 ms 34736 KB Output is correct
9 Correct 251 ms 39600 KB Output is correct
10 Correct 215 ms 37268 KB Output is correct
11 Correct 212 ms 39260 KB Output is correct
12 Incorrect 172 ms 35152 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 46680 KB Output is correct
2 Correct 89 ms 36020 KB Output is correct
3 Correct 80 ms 35512 KB Output is correct
4 Correct 261 ms 38736 KB Output is correct
5 Correct 302 ms 42188 KB Output is correct
6 Correct 179 ms 37472 KB Output is correct
7 Correct 181 ms 37344 KB Output is correct
8 Correct 149 ms 37268 KB Output is correct
9 Correct 136 ms 36948 KB Output is correct
10 Correct 35 ms 20128 KB Output is correct
11 Correct 29 ms 18004 KB Output is correct
12 Correct 32 ms 18392 KB Output is correct
13 Correct 117 ms 45308 KB Output is correct
14 Correct 115 ms 37456 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13148 KB Output is correct
2 Correct 4 ms 13144 KB Output is correct
3 Correct 4 ms 13144 KB Output is correct
4 Correct 5 ms 13148 KB Output is correct
5 Correct 5 ms 13148 KB Output is correct
6 Correct 6 ms 13144 KB Output is correct
7 Correct 5 ms 13148 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 4 ms 13092 KB Output is correct
10 Correct 4 ms 12888 KB Output is correct
11 Correct 4 ms 12888 KB Output is correct
12 Correct 6 ms 13148 KB Output is correct
13 Correct 4 ms 13148 KB Output is correct
14 Incorrect 5 ms 13040 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 46604 KB Output is correct
2 Correct 113 ms 36944 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 31 ms 16288 KB Output is correct
5 Correct 68 ms 33620 KB Output is correct
6 Correct 73 ms 34980 KB Output is correct
7 Correct 77 ms 36676 KB Output is correct
8 Correct 74 ms 34736 KB Output is correct
9 Correct 251 ms 39600 KB Output is correct
10 Correct 215 ms 37268 KB Output is correct
11 Correct 212 ms 39260 KB Output is correct
12 Incorrect 172 ms 35152 KB Output isn't correct
13 Halted 0 ms 0 KB -