191822025-11-28 14:34:17szilProjektcpp17Accepted 100/100273ms21932 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;
const int INF = 1e9;

vector<int> g[MAXN], g2[MAXN];
bool vis[MAXN][4], vis2[MAXN];
int tout[MAXN], timer = 1;

void dfs(int u) {
    vis2[u] = 1;
    for (int v : g[u]) {
        if (!vis2[v]) dfs(v);
    }
    tout[u] = timer++;
}

void dfs_g1(int u, int type) {
    assert(0 <= type && type <= 3);
    vis[u][type] = 1;
    for (int v : g[u]) {
        if (!vis[v][type]) dfs_g1(v, type);
    }
}

void dfs_g2(int u, int type) {
    assert(0 <= type && type <= 3);
    vis[u][type] = 1;
    for (int v : g2[u]) {
        if (!vis[v][type]) dfs_g2(v, type);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, a, b; cin >> n >> m >> a >> b;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g2[v].emplace_back(u);
    }

    dfs_g1(a, 0);
    dfs_g2(a, 1);
    dfs_g1(b, 2);
    dfs_g2(b, 3);

    // 0 a -> u
    // 1 u -> a
    // 2 b -> u
    // 3 u -> b

    vector<int> ans;
    int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt12 = 0, cnt23 = 0, cnt123 = 0;
    vector<int> c1, c2, c3, c12, c23, c123;
    for (int j = 1; j <= n; j++) {
        if (j == a || j == b) continue;
        if (vis[j][1]) {
            cnt1++;
            c1.emplace_back(j);
        }
        else if (vis[j][3] && vis[j][0]) {
            cnt2++;
            c2.emplace_back(j);
        }
        else if (vis[j][2]) {
            cnt3++;
            c3.emplace_back(j);
        }
        else if (vis[j][0]) {
            cnt23++;
            c23.emplace_back(j);
        }
        else if (vis[j][3]) {
            cnt12++;
            c12.emplace_back(j);
        }
        else {
            cnt123++;
            c123.emplace_back(j);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!vis2[i]) dfs(i);
    }

    auto str = [&](vector<int> &todo) {
        sort(todo.begin(), todo.end(), [&](int u, int v){
            return tout[u] < tout[v];
        });
    };

    str(c1);
    str(c2);
    str(c3);
    str(c12);
    str(c23);
    str(c123);
    
    int ans1 = 0, ans2 = 0, ans3 = INF, a1f12 = 0, a2f23 = 0, a1f123 = 0, a2f123 = 0;
    for (int i = 0; i <= cnt12; i++) {
        int x = cnt1 + i;
        int y = cnt2 + (cnt12 - i);
        int z = cnt3;
        int u1f12 = i, u2f23 = 0;
        int left23 = cnt23;
        if (y < z) {
            int used = min(z-y, left23);
            left23 -= used;
            y += used;
            u2f23 += used;
        } else {
            int used = min(y-z, left23);
            left23 -= used;
            z += used;
        }
        if (left23) {
            int used1 = left23 / 2;
            int used2 = (left23 + 1) / 2;
            assert(used1 + used2 == left23);
            y += used1;
            z += used2;
            u2f23 += used1;
        }
        int ox = x, oy = y, oz = z;
        int left123 = cnt123;
        while (left123) {
            if (x < y && x < z) {
                int mx = min(y-x, z-x);
                int used = min(left123, mx);
                x += used;
                left123 -= used;
            } else if (y < x && y < z) {
                int mx = min(x-y, z-y);
                int used = min(left123, mx);
                y += used;
                left123 -= used;
            } else if (z < x && z < y) {
                int mx = min(x-z, y-z);
                int used = min(left123, mx);
                z += used;
                left123 -= used;
            } else if (x == y && y == z) {
                int used1 = left123 / 3;
                int used2 = left123 / 3;
                int used3 = left123 / 3;
                int tot = used1 + used2 + used3;
                if (tot + 1 == left123) used1++;
                else if (tot + 2 == left123) {
                    used1++;
                    used2++;
                }
                x += used1;
                y += used2;
                z += used3;
                left123 = 0;
            } else {
                if (left123 == 1) {
                    if (x == y) x++;
                    else if (x == z) x++;
                    else y++;
                    break;
                } else if (x == y) {
                    int mx = z-x;
                    int used = min(mx, left123/2);
                    x += used;
                    y += used;
                    left123 -= 2*used;
                } else if (x == z) {
                    int mx = y-x;
                    int used = min(mx, left123/2);
                    x += used;
                    z += used;
                    left123 -= 2*used;
                } else if (y == z) {
                    int mx = x-y;
                    int used = min(mx, left123/2);
                    y += used;
                    z += used;
                    left123 -= 2*used;
                } else throw 1;
            }
        }
        int u1f123 = x-ox;
        int u2f123 = y-oy;
        if (max({ans1, ans2, ans3}) - min({ans1, ans2, ans3}) > max({x, y, z}) - min({x, y, z})) {
            ans1 = x;
            ans2 = y;
            ans3 = z;
            a1f12 = u1f12;
            a2f23 = u2f23;
            a1f123 = u1f123;
            a2f123 = u2f123;
        }
    }
    
    cout << ans1 << " " << ans2 << " " << ans3 << "\n";

    vector<int> comp1, comp2, comp3;
    int a2f12 = cnt12 - a1f12;
    int a3f23 = cnt23 - a2f23;
    int a3f123 = cnt123 - a1f123 - a2f123;
    auto work = [](int cnt, vector<int> &from, vector<int> &to) {
        for (int i = 0; i < cnt; i++) {
            to.emplace_back(from.back());
            from.pop_back();
        }
    };
    work(cnt1, c1, comp1);
    work(a1f12, c12, comp1);
    work(a1f123, c123, comp1);
    work(cnt2, c2, comp2);
    work(a2f12, c12, comp2);
    work(a2f23, c23, comp2);
    work(a2f123, c123, comp2);
    work(a3f23, c23, comp3);
    work(cnt3, c3, comp3);
    work(a3f123, c123, comp3);
    
    for (auto vec : {c1, c2, c3, c12, c23, c123}) {
        assert(vec.empty());
    }

    auto st = [&](vector<int> &todo) {
        sort(todo.begin(), todo.end(), [&](int u, int v){
            return tout[u] > tout[v];
        });
    };

    st(comp1);
    st(comp2);
    st(comp3);

    assert(comp1.size() == ans1);
    assert(comp2.size() == ans2);
    assert(comp3.size() == ans3);

    vector<int> res;

    for (int i : comp1) res.emplace_back(i);
    res.emplace_back(a);
    for (int i : comp2) res.emplace_back(i);
    res.emplace_back(b);
    for (int i : comp3) res.emplace_back(i);

    vector<int> idx(n+1);
    for (int i = 0; i < n; i++) {
        idx[res[i]] = i;
    }

    vector<bool> done(n+1);

    for (int i = 0; i < n; i++) {
        while (!g2[res[i]].empty()) {
            int j = g2[res[i]].back();
            g2[res[i]].pop_back();
            if (!done[j]) {
                int b1 = res[i];
                int b2 = j;
                swap(res[idx[b1]], res[idx[b2]]);
                swap(idx[b1], idx[b2]);
                break;
            }
        }
        done[res[i]] = 1;
    }

    // assert(ok);

    for (int i : res) cout << i << " ";

    // cerr << cnt1 << " " << cnt2 << " " << cnt3 << " " << cnt12 << " " << cnt23 << " " << cnt123 << endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms4916 KiB
2Accepted78ms11956 KiB
subtask215/15
3Accepted7ms5172 KiB
4Accepted8ms5172 KiB
5Accepted10ms5428 KiB
6Accepted24ms6452 KiB
7Accepted41ms7948 KiB
8Accepted65ms9744 KiB
9Accepted90ms11184 KiB
10Accepted181ms18200 KiB
11Accepted273ms20528 KiB
12Accepted273ms20392 KiB
subtask315/15
13Accepted4ms4920 KiB
14Accepted6ms4916 KiB
15Accepted4ms5108 KiB
16Accepted6ms4916 KiB
17Accepted4ms4916 KiB
18Accepted4ms5044 KiB
19Accepted6ms5128 KiB
20Accepted4ms5132 KiB
21Accepted4ms4916 KiB
22Accepted6ms4928 KiB
23Accepted4ms5124 KiB
24Accepted6ms4916 KiB
25Accepted4ms4948 KiB
26Accepted6ms5172 KiB
27Accepted4ms5108 KiB
28Accepted6ms5048 KiB
29Accepted4ms4916 KiB
30Accepted6ms4980 KiB
31Accepted6ms4916 KiB
subtask415/15
32Accepted4ms4920 KiB
33Accepted6ms4916 KiB
34Accepted4ms5108 KiB
35Accepted6ms4916 KiB
36Accepted4ms4916 KiB
37Accepted4ms5044 KiB
38Accepted6ms5128 KiB
39Accepted4ms5132 KiB
40Accepted4ms4916 KiB
41Accepted6ms4928 KiB
42Accepted4ms5124 KiB
43Accepted6ms4916 KiB
44Accepted4ms4948 KiB
45Accepted6ms5172 KiB
46Accepted4ms5108 KiB
47Accepted10ms5684 KiB
48Accepted10ms5684 KiB
49Accepted13ms5944 KiB
50Accepted14ms5940 KiB
51Accepted13ms5920 KiB
52Accepted13ms5940 KiB
53Accepted13ms5952 KiB
54Accepted10ms5684 KiB
55Accepted9ms5684 KiB
56Accepted8ms5428 KiB
57Accepted6ms5048 KiB
58Accepted4ms4916 KiB
59Accepted6ms4980 KiB
60Accepted6ms4916 KiB
subtask515/15
61Accepted4ms4916 KiB
62Accepted6ms4928 KiB
63Accepted10ms5684 KiB
64Accepted14ms5940 KiB
65Accepted13ms5920 KiB
66Accepted92ms13396 KiB
67Accepted86ms13036 KiB
68Accepted90ms12460 KiB
69Accepted93ms12812 KiB
70Accepted68ms11436 KiB
71Accepted97ms13992 KiB
72Accepted101ms12848 KiB
73Accepted118ms14060 KiB
74Accepted71ms11692 KiB
75Accepted90ms13456 KiB
76Accepted57ms9916 KiB
77Accepted103ms13064 KiB
78Accepted119ms13996 KiB
79Accepted94ms14252 KiB
80Accepted231ms21932 KiB
81Accepted6ms5048 KiB
82Accepted4ms4916 KiB
subtask640/40
83Accepted4ms5108 KiB
84Accepted103ms11948 KiB
85Accepted4ms4920 KiB
86Accepted6ms4916 KiB
87Accepted4ms5108 KiB
88Accepted6ms4916 KiB
89Accepted4ms4916 KiB
90Accepted4ms5044 KiB
91Accepted6ms5128 KiB
92Accepted4ms5132 KiB
93Accepted4ms4916 KiB
94Accepted6ms4928 KiB
95Accepted4ms5124 KiB
96Accepted6ms4916 KiB
97Accepted4ms4948 KiB
98Accepted6ms5172 KiB
99Accepted4ms5108 KiB
100Accepted10ms5684 KiB
101Accepted10ms5684 KiB
102Accepted13ms5944 KiB
103Accepted14ms5940 KiB
104Accepted13ms5920 KiB
105Accepted13ms5940 KiB
106Accepted13ms5952 KiB
107Accepted10ms5684 KiB
108Accepted9ms5684 KiB
109Accepted8ms5428 KiB
110Accepted92ms13396 KiB
111Accepted41ms8624 KiB
112Accepted86ms13036 KiB
113Accepted90ms12460 KiB
114Accepted93ms12812 KiB
115Accepted68ms11436 KiB
116Accepted97ms13992 KiB
117Accepted101ms12848 KiB
118Accepted118ms14060 KiB
119Accepted71ms11692 KiB
120Accepted90ms13456 KiB
121Accepted57ms9916 KiB
122Accepted103ms13064 KiB
123Accepted114ms13520 KiB
124Accepted93ms13848 KiB
125Accepted93ms13484 KiB
126Accepted37ms8368 KiB
127Accepted74ms11244 KiB
128Accepted76ms12416 KiB
129Accepted71ms11248 KiB
130Accepted94ms13636 KiB
131Accepted65ms11252 KiB
132Accepted90ms12716 KiB
133Accepted119ms14252 KiB
134Accepted93ms13484 KiB
135Accepted79ms12460 KiB
136Accepted119ms13996 KiB
137Accepted116ms14252 KiB
138Accepted70ms11400 KiB
139Accepted90ms13236 KiB
140Accepted108ms13904 KiB
141Accepted115ms13996 KiB
142Accepted86ms13188 KiB
143Accepted94ms14252 KiB
144Accepted231ms21932 KiB
145Accepted7ms5172 KiB
146Accepted8ms5172 KiB
147Accepted10ms5428 KiB
148Accepted24ms6452 KiB
149Accepted41ms7948 KiB
150Accepted65ms9744 KiB
151Accepted90ms11184 KiB
152Accepted181ms18200 KiB
153Accepted273ms20528 KiB
154Accepted273ms20392 KiB
155Accepted6ms5048 KiB
156Accepted4ms4916 KiB
157Accepted6ms4980 KiB
158Accepted6ms4916 KiB