Tutorial for Codeforces 1369E

Solution #

First let’s find $s_i$ : the number of friends who love food $i$ . For some food $i$ , if $s_i\leq w_i$ , we can see that all the friends who love $i$ will have food to eat no matter what order you call them. So we want to call them as late as possible.

The solution is like doing a topological sort or BFS: we start from all the $i$ that $s_i\leq w_i$ . When visiting a new vertex $u$ , decrease $s_u$ by one and then if $s_u\leq w_u$ , put $u$ in the queue and put it in the call list. Finally we reverse our call list and that’s the answer.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define pb push_back
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int> a(n),deg(n);
    for(auto& i:a) cin>>i;
    vector<vector<pii>> G(n);
    forn(i,m){
        int x,y;
        cin>>x>>y;
        x--,y--;
        deg[x]++,deg[y]++;
        G[x].pb({y,i});
        G[y].pb({x,i});
    }
    vector<int> ans;
    vector<int> vis(m);
    queue<int> q;
    forn(i,n){
        if(deg[i]<=a[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto [to,i]:G[u]){
            if(!vis[i]){
                ans.pb(i+1);
                vis[i]=1;
                deg[to]--;
                if(deg[to]<=a[to]) q.push(to);
            }
        }
    }
    if(sz(ans)!=m) return cout<<"DEAD",0;
    reverse(all(ans));
    cout<<"ALIVE\n";
    for(auto it:ans) cout<<it<<' ';
    return 0;
}

Tutorial for Codeforces 1369E - DeadLee

Solution #

Code #