191822025-11-28 14:34:17szilProjektcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms4916 KiB
2Elfogadva78ms11956 KiB
subtask215/15
3Elfogadva7ms5172 KiB
4Elfogadva8ms5172 KiB
5Elfogadva10ms5428 KiB
6Elfogadva24ms6452 KiB
7Elfogadva41ms7948 KiB
8Elfogadva65ms9744 KiB
9Elfogadva90ms11184 KiB
10Elfogadva181ms18200 KiB
11Elfogadva273ms20528 KiB
12Elfogadva273ms20392 KiB
subtask315/15
13Elfogadva4ms4920 KiB
14Elfogadva6ms4916 KiB
15Elfogadva4ms5108 KiB
16Elfogadva6ms4916 KiB
17Elfogadva4ms4916 KiB
18Elfogadva4ms5044 KiB
19Elfogadva6ms5128 KiB
20Elfogadva4ms5132 KiB
21Elfogadva4ms4916 KiB
22Elfogadva6ms4928 KiB
23Elfogadva4ms5124 KiB
24Elfogadva6ms4916 KiB
25Elfogadva4ms4948 KiB
26Elfogadva6ms5172 KiB
27Elfogadva4ms5108 KiB
28Elfogadva6ms5048 KiB
29Elfogadva4ms4916 KiB
30Elfogadva6ms4980 KiB
31Elfogadva6ms4916 KiB
subtask415/15
32Elfogadva4ms4920 KiB
33Elfogadva6ms4916 KiB
34Elfogadva4ms5108 KiB
35Elfogadva6ms4916 KiB
36Elfogadva4ms4916 KiB
37Elfogadva4ms5044 KiB
38Elfogadva6ms5128 KiB
39Elfogadva4ms5132 KiB
40Elfogadva4ms4916 KiB
41Elfogadva6ms4928 KiB
42Elfogadva4ms5124 KiB
43Elfogadva6ms4916 KiB
44Elfogadva4ms4948 KiB
45Elfogadva6ms5172 KiB
46Elfogadva4ms5108 KiB
47Elfogadva10ms5684 KiB
48Elfogadva10ms5684 KiB
49Elfogadva13ms5944 KiB
50Elfogadva14ms5940 KiB
51Elfogadva13ms5920 KiB
52Elfogadva13ms5940 KiB
53Elfogadva13ms5952 KiB
54Elfogadva10ms5684 KiB
55Elfogadva9ms5684 KiB
56Elfogadva8ms5428 KiB
57Elfogadva6ms5048 KiB
58Elfogadva4ms4916 KiB
59Elfogadva6ms4980 KiB
60Elfogadva6ms4916 KiB
subtask515/15
61Elfogadva4ms4916 KiB
62Elfogadva6ms4928 KiB
63Elfogadva10ms5684 KiB
64Elfogadva14ms5940 KiB
65Elfogadva13ms5920 KiB
66Elfogadva92ms13396 KiB
67Elfogadva86ms13036 KiB
68Elfogadva90ms12460 KiB
69Elfogadva93ms12812 KiB
70Elfogadva68ms11436 KiB
71Elfogadva97ms13992 KiB
72Elfogadva101ms12848 KiB
73Elfogadva118ms14060 KiB
74Elfogadva71ms11692 KiB
75Elfogadva90ms13456 KiB
76Elfogadva57ms9916 KiB
77Elfogadva103ms13064 KiB
78Elfogadva119ms13996 KiB
79Elfogadva94ms14252 KiB
80Elfogadva231ms21932 KiB
81Elfogadva6ms5048 KiB
82Elfogadva4ms4916 KiB
subtask640/40
83Elfogadva4ms5108 KiB
84Elfogadva103ms11948 KiB
85Elfogadva4ms4920 KiB
86Elfogadva6ms4916 KiB
87Elfogadva4ms5108 KiB
88Elfogadva6ms4916 KiB
89Elfogadva4ms4916 KiB
90Elfogadva4ms5044 KiB
91Elfogadva6ms5128 KiB
92Elfogadva4ms5132 KiB
93Elfogadva4ms4916 KiB
94Elfogadva6ms4928 KiB
95Elfogadva4ms5124 KiB
96Elfogadva6ms4916 KiB
97Elfogadva4ms4948 KiB
98Elfogadva6ms5172 KiB
99Elfogadva4ms5108 KiB
100Elfogadva10ms5684 KiB
101Elfogadva10ms5684 KiB
102Elfogadva13ms5944 KiB
103Elfogadva14ms5940 KiB
104Elfogadva13ms5920 KiB
105Elfogadva13ms5940 KiB
106Elfogadva13ms5952 KiB
107Elfogadva10ms5684 KiB
108Elfogadva9ms5684 KiB
109Elfogadva8ms5428 KiB
110Elfogadva92ms13396 KiB
111Elfogadva41ms8624 KiB
112Elfogadva86ms13036 KiB
113Elfogadva90ms12460 KiB
114Elfogadva93ms12812 KiB
115Elfogadva68ms11436 KiB
116Elfogadva97ms13992 KiB
117Elfogadva101ms12848 KiB
118Elfogadva118ms14060 KiB
119Elfogadva71ms11692 KiB
120Elfogadva90ms13456 KiB
121Elfogadva57ms9916 KiB
122Elfogadva103ms13064 KiB
123Elfogadva114ms13520 KiB
124Elfogadva93ms13848 KiB
125Elfogadva93ms13484 KiB
126Elfogadva37ms8368 KiB
127Elfogadva74ms11244 KiB
128Elfogadva76ms12416 KiB
129Elfogadva71ms11248 KiB
130Elfogadva94ms13636 KiB
131Elfogadva65ms11252 KiB
132Elfogadva90ms12716 KiB
133Elfogadva119ms14252 KiB
134Elfogadva93ms13484 KiB
135Elfogadva79ms12460 KiB
136Elfogadva119ms13996 KiB
137Elfogadva116ms14252 KiB
138Elfogadva70ms11400 KiB
139Elfogadva90ms13236 KiB
140Elfogadva108ms13904 KiB
141Elfogadva115ms13996 KiB
142Elfogadva86ms13188 KiB
143Elfogadva94ms14252 KiB
144Elfogadva231ms21932 KiB
145Elfogadva7ms5172 KiB
146Elfogadva8ms5172 KiB
147Elfogadva10ms5428 KiB
148Elfogadva24ms6452 KiB
149Elfogadva41ms7948 KiB
150Elfogadva65ms9744 KiB
151Elfogadva90ms11184 KiB
152Elfogadva181ms18200 KiB
153Elfogadva273ms20528 KiB
154Elfogadva273ms20392 KiB
155Elfogadva6ms5048 KiB
156Elfogadva4ms4916 KiB
157Elfogadva6ms4980 KiB
158Elfogadva6ms4916 KiB