제출 #1328991

#제출 시각아이디문제언어결과실행 시간메모리
1328991rana_azkaPovjerenstvo (COI22_povjerenstvo)C++20
0 / 100
3099 ms140380 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 5e5;

int n, m;
vector<int> adj[MAXN+5];
int inDegree[MAXN+5];
int visited[MAXN+5];
int dp[5][MAXN+5];
vector<pair<int, int>> pre[5][MAXN+5];
int entered[MAXN+5];

set<int> ans;
void backtrack(pair<int, bool> yey){
    auto [cur, stat] = yey;
    // cerr << "backtrack : " << cur << ' ' << stat << endl;
    if(stat) ans.insert(cur);
    
    for(auto i : pre[stat][cur]) backtrack(i);
}

void debug(){
    cerr << "\nADJ" << endl;
    for(int i = 1; i <= n; i++){
        cerr << i << " : ";
        for(auto j : adj[i]) cerr << j << ' ';
        cerr << endl;
    }

    cerr << "\nDP" << endl;
    for(int i = 1; i <= n; i++){
        cerr << i << " : " << dp[0][i] << ' ' << dp[1][i] << endl;
    }

    cerr << "\nPRE" << endl;
    for(int i = 1; i <= n; i++){
        cerr << i << ' ' << 0 << " : ";
        for(auto j : pre[0][i]) cerr << j.first << ' ' << j.second << ' ';
        cerr << endl;

        cerr << i << ' ' << 1 << " : ";
        for(auto j : pre[1][i]) cerr << j.first << ' ' << j.second << ' ';
        cerr << endl;
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        adj[v].push_back(u);
        inDegree[u]++;
    }

    queue<int> bfs;
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0) bfs.push(i);
    }

    vector<int> lastNode;
    while(!bfs.empty()){
        int cur = bfs.front();
        bfs.pop();

        // cerr << "cur : " << cur << endl;
        if(visited[cur]) continue;
        visited[cur] = 1;

        dp[1][cur]++;
        
        bool isLastNode = 1;
        for(auto next : adj[cur]){
            if(visited[next]) continue;
            isLastNode = 0;
            // cerr << "next : " << next << endl;

            if(dp[0][cur] > dp[1][cur]){
                dp[0][next] += dp[0][cur];
                pre[0][next].push_back({cur, 0});
            }else{
                dp[0][next] += dp[1][cur];
                pre[0][next].push_back({cur, 1});
            }

            dp[1][next] += dp[0][cur];
            pre[1][next].push_back({cur, 0});

            entered[next]++;
            if(entered[next] >= inDegree[next]) bfs.push(next);
        }

        if(isLastNode) lastNode.push_back(cur);
    }

    for(auto i : lastNode){
        // cerr << "lastNode : " << i << endl;
        if(dp[0][i] > dp[1][i]) backtrack({i, 0});
        else backtrack({i, 1});
    }

    cout << ans.size() << endl;
    for(auto i : ans) cout << i << ' ';
    cout << endl;

    // debug();
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        solve();
    }

    return 0;
}

/*
4 3
1 2
1 3
2 4
=> 2 {4, 1}

4 4
1 2
1 3
2 4
3 4
=> 2 {4, 1}
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...