Submission #1297159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297159		tab	Naboj (COCI22_naboj)	C++20	0 / 110	54 ms	11028 KiB

naboj

#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second

const intt mxN = 1e5 + 5;
const intt LG = 20;
const intt inf = 1e18;  

intt n,c;
vector<vector<intt>> graph;
vector<intt> color(mxN);

void dfs(intt node) {
    color[node] = 1;
    for(auto u : graph[node]) {
        if(color[u] == 0) {
            dfs(u);
        } else if(color[u] == 1) {
            c=1;
            return;
        }
    }
    color[node] = 2;
}

vector<intt> boo;
void dfs2(intt node) {
    color[node]=1;
    for(auto u : graph[node]) {
        if(!color[u]) {
            dfs2(u);
        }
    }
    boo.push_back(node);
}

void _() {
    cin >> n;
    graph.assign(n + 1, vector<intt> {});
    color.assign(n + 1, 0ll);
    for(intt i = 1; i <= n - 1; i++) {
        intt a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    for(intt i = 1; i <= n; i++) {
        if(!color[i]) {
            dfs(i);
            if(c)break;
        }
    }
    if(c) {
        cout << -1 << endl;
        return;
    }
    color.assign(n + 1, 0ll);
    for(intt i = 1; i <= n; i++) {
        if(!color[i]) {
            dfs2(i);
        }
    }
    cout << boo.size() << endl;
    for(intt i = 0; i < boo.size(); i++) {
        cout << boo[i] << " 0" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << "Case #" << buu++ << ": ";
        _();
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 25
• Subtask 3: 0 / 70