Submission #870561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870561	2023-11-08T10:00:41 Z	Tigerpants	Link (CEOI06_link)	C++17	24 / 100	377 ms	67440 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	1 ms	348 KB	Output isn't correct
4	Correct	1 ms	604 KB	Output is correct
5	Incorrect	2 ms	1048 KB	Output isn't correct
6	Incorrect	9 ms	4188 KB	Output isn't correct
7	Incorrect	15 ms	6748 KB	Output isn't correct
8	Incorrect	20 ms	9552 KB	Output isn't correct
9	Correct	36 ms	14688 KB	Output is correct
10	Incorrect	32 ms	13396 KB	Output isn't correct
11	Correct	64 ms	20820 KB	Output is correct
12	Incorrect	99 ms	26452 KB	Output isn't correct
13	Correct	152 ms	34508 KB	Output is correct
14	Incorrect	205 ms	39824 KB	Output isn't correct
15	Incorrect	229 ms	46920 KB	Output isn't correct
16	Incorrect	320 ms	53308 KB	Output isn't correct
17	Incorrect	325 ms	60220 KB	Output isn't correct
18	Incorrect	377 ms	65916 KB	Output isn't correct
19	Correct	360 ms	66132 KB	Output is correct
20	Incorrect	369 ms	67164 KB	Output isn't correct
21	Incorrect	367 ms	66776 KB	Output isn't correct
22	Incorrect	369 ms	67440 KB	Output isn't correct
23	Incorrect	360 ms	67040 KB	Output isn't correct
24	Incorrect	373 ms	66644 KB	Output isn't correct
25	Incorrect	365 ms	66640 KB	Output isn't correct