Submission #870561

#	Time	Username	Problem	Language	Result	Execution time	Memory
870561		Tigerpants	Link (CEOI06_link)	C++17	24 / 100	377 ms	67440 KiB

link

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef set<ll> sll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define sz(a) (ll) a.size()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)

ll N, K;
vvll g;
vvll rev_g;
vll propagate;
vb reached;

sll starts;

ll answ = 0;

void dfs(ll cur, bool force = false) {
    if (reached[cur]) return;

    if (!force) {
        for (vll::iterator pre = rev_g[cur].begin(); pre != rev_g[cur].end(); pre++) {
            if (!reached[*pre]) {
                //cout << "pre " << *pre + 1 << " (" << cur + 1 << ")" << endl;
                return;
            }
        }

        if (propagate[cur] == 0) {
            starts.insert(cur);
            //cout << "make s " << cur + 1 << endl;
            return;
        }
    }

    reached[cur] = true;

    for (vll::iterator nxt = g[cur].begin(); nxt != g[cur].end(); nxt++) {
        propagate[*nxt] = max<ll>(propagate[*nxt], propagate[cur] - 1);
        //cout << cur + 1 << " : " << *nxt + 1 << " (" << propagate[*nxt] << ")" << endl;
        dfs(*nxt);
    }
}

void iterate_starts() {
    while (!starts.empty()) {
        ll cur = *starts.begin(); starts.erase(starts.begin());
        answ++;
        //cout << "1 --> " << cur + 1 << endl;

        propagate[cur] = K;
        dfs(cur);
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);

    cin >> N >> K;

    g.resize(N);
    rev_g.resize(N);
    propagate.resize(N, 0);
    reached.resize(N, false);

    rep(i, 0, N) {
        ll tmpu, tmpv;
        cin >> tmpu >> tmpv;
        tmpu--; tmpv--;
        g[tmpu].pb(tmpv);
        rev_g[tmpv].pb(tmpu);
    }

    propagate[0] = K + 1;
    dfs(0, true);

    rep(i, 1, N) {
        if (sz(rev_g[i]) == 0) {
            starts.insert(i);
        }
    }

    iterate_starts();

    // push propagate
    rep(i, 0, N) {
        if (propagate[i] != 0) {
            dfs(i, true);
            iterate_starts();
        }
    }

    // take care of closed loops without entry points...
    rep(i, 0, N) {
        if (!reached[i]) {
            propagate[i] = K;
            answ++;
            //cout << "1 --> " << i + 1 << endl;
            dfs(i, true);
            iterate_starts();
        }
    }

    // output answer
    cout << answ << endl;

    return 0;
}

• Subtask 1: 24 / 100