Submission #1328975

#TimeUsernameProblemLanguageResultExecution timeMemory
1328975rana_azkaPovjerenstvo (COI22_povjerenstvo)C++20
0 / 100
243 ms162716 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 par[MAXN+5];
int dp[5][MAXN+5];
vector<pair<int, bool>> pre[5][MAXN+5];

void dfs(int cur){
    dp[1][cur] += 1;
    for(auto next : adj[cur]){
        if(next == par[cur]) continue;

        dfs(next);
        dp[0][cur] += max(dp[0][next], dp[1][next]);
        dp[1][cur] += dp[0][next];

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

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

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

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(inDegree[i] > 0) continue;
        dfs(i);
        ans += max(dp[0][i], dp[1][i]);
    }

    for(int i = 1; i <= n; i++){
        if(inDegree[i] > 0) continue;
        // cerr << "masuk : " << i << endl;
        if(dp[0][i] > dp[1][i]) backtrack({i, 0});
        else backtrack({i, 1});
    }

    cout << ans << endl;
    for(auto i : st) cout << i << ' ';
    cout << 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;
    // }
}

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...