oj.uz

답안 #883730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883730 2023-12-05T21:17:36 Z Dec0Dedd 자매 도시 (APIO20_swap) C++14
100 / 100
 725 ms 164372 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 3e5+10;
const int K = 20;
const int INF = 1e9+10;

vector<pii> G[N], add[N];
int n, m, a[N], b[N], dpdwn[N], dpup[N];

vector<pii> ed;

struct dsu {
    vector<int> p;

    void init(int sz) {
        p.resize(sz+10);
        for (int i=0; i<sz+10; ++i) p[i]=i;
    }

    int f(int x) {
        if (p[x] == x) return x;
        return p[x]=f(p[x]);
    }

    void mrg(int x, int y) {
        x=f(x), y=f(y);
        if (x == y) return;
        p[x]=y;
    }
};

dsu d;

int up[K][N], mx[K][N], mxd[K][N], tin[N], tout[N], dwn[N], pvl[N], t;
multiset<int> ms[N];
vector<int> ds[N], wgs[N];

void dfs(int v, int p, int w, int mwo) {
    up[0][v]=p, mx[0][v]=w, mxd[0][v]=mwo, tin[v]=++t;
    for (int j=1; j<K; ++j) up[j][v]=up[j-1][up[j-1][v]];
    for (int j=1; j<K; ++j) mx[j][v]=max(mx[j-1][v], mx[j-1][up[j-1][v]]);
    for (int j=1; j<K; ++j) mxd[j][v]=min(mxd[j-1][v], mxd[j-1][up[j-1][v]]);
    dwn[v]=INF;

    for (auto u : G[v]) {
        if (u.second == p) continue;
        wgs[v].push_back(u.first);
        ms[v].insert(u.first);
    } sort(wgs[v].begin(), wgs[v].end());

    if ((int)wgs[v].size() >= 2) dwn[v]=max(wgs[v][0], wgs[v][1]);

    for (auto u : G[v]) {
        if (u.second == p) continue;
        int k;
        if (wgs[v][0] == u.first) {
            if ((int)wgs[v].size() == 1) k=INF;
            else k=wgs[v][1]; 
        } else k=wgs[v][0];
        dfs(u.second, v, u.first, k);
        if (dwn[u.second] < INF) dwn[v]=min(dwn[v], max(dwn[u.second], u.first));
        ds[v].push_back(max(dwn[u.second], u.first));
    } tout[v]=t++, sort(ds[v].begin(), ds[v].end());
}

void dfs2(int v, int p, int ppk) {
    pvl[v]=ppk;
    if (v != 1) pvl[v]=max(pvl[v], mx[0][v]);

    for (auto u : G[v]) {
        if (u.second == p) continue;
        int tmp=pvl[v];
        if ((int)wgs[v].size() >= 3) {
            if (u.first == wgs[v][0]) tmp=min(tmp, wgs[v][2]); // wgs[1], wgs[2]
            else if (u.first == wgs[v][1]) tmp=min(tmp, wgs[v][2]); // wgs[0], wgs[2]
            else tmp=min(tmp, wgs[v][1]); // wgs[0], wgs[1]
        }

        if (v != 1 && (int)wgs[v].size() >= 2) {
            if (u.first == wgs[v][0]) tmp=min(tmp, max(wgs[v][1], mx[0][v]));
            else tmp=min(tmp, max(wgs[v][0], mx[0][v]));
        }

        if ((int)ds[v].size() >= 2) {
            if (dwn[u.second] == ds[v][0]) tmp=min(tmp, ds[v][1]);
            else tmp=min(tmp, ds[v][0]);
        } dfs2(u.second, v, tmp);
    }
}

void dfs3(int v, int p) {
    dpdwn[v]=INF;
    for (auto u : G[v]) {
        if (u.second == p) continue;
        dfs3(u.second, v);
        dpdwn[v]=min(dpdwn[v], max(dpdwn[u.second], u.first));
    }

    for (auto u : add[v]) dpdwn[v]=min(dpdwn[v], u.first);
}

void dfs4(int v, int p, int px) {
    dpup[v]=px;

    vector<int> dps;
    for (auto u : G[v]) {
        if (u.second == p) continue;
        dps.push_back(max(dpdwn[u.second], u.first));
    } sort(dps.begin(), dps.end());

    for (auto u : add[v]) dpup[v]=min(dpup[v], u.first);
    for (auto u : G[v]) {
        if (u.second == p) continue;
        int tp=dpup[v];
        if ((int)dps.size() >= 2) {
            if (dps[0] == max(dpdwn[u.second], u.first)) tp=min(tp, dps[1]);
            else tp=min(tp, dps[0]);
        } dfs4(u.second, v, max(u.first, tp));
    }
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca(int v, int u) {
    if (anc(v, u)) return v;
    if (anc(u, v)) return u;
    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][v], u)) v=up[j][v];
    } return up[0][v];
}

int mwp(int v, int u) {
    int l=lca(v, u);

    int cv=v, cu=u, res=0;
    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cv], u)) {
            res=max(res, mx[j][cv]);
            cv=up[j][cv];
        }
    }

    if (cv != l) res=max(res, mx[0][cv]);

    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cu], v)) {
            res=max(res, mx[j][cu]);
            cu=up[j][cu];
        }
    }

    if (cu != l) res=max(res, mx[0][cu]);
    return res;
}

int mwo(int v, int u) {
    int l=lca(v, u);

    if (v == l) swap(v, u);
    int cv=v, cu=u, res=dwn[v];
    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cv], u)) {
            res=min(res, mxd[j][cv]);
            cv=up[j][cv];
        }
    }

    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cu], v)) {
            res=min(res, mxd[j][cu]);
            cu=up[j][cu];
        }
    }

    if (u == l) {
        res=min(res, dwn[v]);

        int tpw=mx[0][cv];

        int k;
        if (u == 1) k=INF;
        else k=mx[0][u];

        if (u != 1) res=min(res, max(k, pvl[u]));

        //cout<<"HERE "<<u<<" || "<<k<<" || "<<pvl[u]<<"\n";

        if ((int)wgs[u].size() >= 3) {
            if (tpw == wgs[u][0]) res=min(res, wgs[u][2]); // wgs[1], wgs[2]
            else if (tpw == wgs[u][1]) res=min(res, wgs[u][2]); // wgs[0], wgs[2]
            else res=min(res, wgs[u][1]); // wgs[0], wgs[1]
        }

        if (k < INF && (int)wgs[u].size() >= 2) {
            if (tpw == wgs[u][0]) res=min(res, max(wgs[u][1], k)); // wgs[1], k
            else res=min(res, max(wgs[u][0], k));
        }

        //cout<<"size "<<ds[u].size()<<" ==> "<<ds[u][0]<<", "<<ds[u][1]<<"\n";
        if ((int)ds[u].size() >= 2) {
            if (dwn[cv] == ds[u][0]) res=min(res, ds[u][1]);
            else res=min(res, ds[u][0]);
        }
    } else {
        res=min(res, dwn[u]);
        if (l != 1) res=min(res, mx[0][l]);
        res=min({res, dwn[v], dwn[u]});

        int au=-1, av=-1;
        av=mx[0][cv], ms[l].erase(ms[l].find(mx[0][cv]));
        au=mx[0][cu], ms[l].erase(ms[l].find(mx[0][cu]));
        if (!ms[l].empty()) res=min(res, *ms[l].begin());
        ms[l].insert(au), ms[l].insert(av);
    } return res;
}

bool ok=false;
void init(int _n, int _m, vector<int> x, vector<int> y, vector<int> w) {
    n=_n, m=_m;
    for (int i=0; i<m; ++i) {
        ++x[i], ++y[i];
        a[i+1]=x[i], b[i+1]=y[i];
        ed.push_back({w[i], i+1});
    } sort(ed.begin(), ed.end());

    d.init(n+10);
    for (auto u : ed) {
        if (d.f(a[u.second]) == d.f(b[u.second])) {
            add[a[u.second]].push_back({u.first, b[u.second]});
            add[b[u.second]].push_back({u.first, a[u.second]});
        } else {
            d.mrg(a[u.second], b[u.second]);
            G[a[u.second]].push_back({u.first, b[u.second]});
            G[b[u.second]].push_back({u.first, a[u.second]});
        }
    } dfs(1, 1, 0, INF);
    dfs2(1, 1, INF);
    dfs3(1, 1);
    dfs4(1, 1, INF);
}

int getMinimumFuelCapacity(int x, int y) {
    ++x, ++y;
    if (d.f(x) != d.f(y)) return -1;
    int val=max(mwp(x, y), min({mwo(x, y), dpup[x], dpup[y], dpdwn[x], dpdwn[y]}));
    if (val >= INF) return -1;
    return val;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 122452 KB Output is correct
2 Correct 18 ms 122460 KB Output is correct
3 Correct 17 ms 122464 KB Output is correct
4 Correct 18 ms 122448 KB Output is correct
5 Correct 19 ms 122712 KB Output is correct
6 Correct 19 ms 122716 KB Output is correct
7 Correct 20 ms 122828 KB Output is correct
8 Correct 21 ms 122716 KB Output is correct
9 Correct 165 ms 146888 KB Output is correct
10 Correct 232 ms 155588 KB Output is correct
11 Correct 221 ms 153820 KB Output is correct
12 Correct 230 ms 156356 KB Output is correct
13 Correct 213 ms 160760 KB Output is correct
14 Correct 200 ms 145864 KB Output is correct
15 Correct 507 ms 158976 KB Output is correct
16 Correct 541 ms 154240 KB Output is correct
17 Correct 519 ms 164372 KB Output is correct
18 Correct 508 ms 161156 KB Output is correct
19 Correct 156 ms 133572 KB Output is correct
20 Correct 532 ms 157872 KB Output is correct
21 Correct 499 ms 154988 KB Output is correct
22 Correct 634 ms 159904 KB Output is correct
23 Correct 520 ms 161036 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 122452 KB Output is correct
2 Correct 18 ms 122460 KB Output is correct
3 Correct 476 ms 142856 KB Output is correct
4 Correct 465 ms 143660 KB Output is correct
5 Correct 504 ms 143424 KB Output is correct
6 Correct 485 ms 143660 KB Output is correct
7 Correct 477 ms 143412 KB Output is correct
8 Correct 492 ms 142724 KB Output is correct
9 Correct 530 ms 143304 KB Output is correct
10 Correct 537 ms 142664 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 122452 KB Output is correct
2 Correct 18 ms 122460 KB Output is correct
3 Correct 17 ms 122464 KB Output is correct
4 Correct 18 ms 122448 KB Output is correct
5 Correct 19 ms 122712 KB Output is correct
6 Correct 19 ms 122716 KB Output is correct
7 Correct 20 ms 122828 KB Output is correct
8 Correct 21 ms 122716 KB Output is correct
9 Correct 18 ms 122456 KB Output is correct
10 Correct 19 ms 122716 KB Output is correct
11 Correct 19 ms 122796 KB Output is correct
12 Correct 18 ms 122716 KB Output is correct
13 Correct 19 ms 122728 KB Output is correct
14 Correct 18 ms 122456 KB Output is correct
15 Correct 19 ms 122716 KB Output is correct
16 Correct 19 ms 122712 KB Output is correct
17 Correct 18 ms 122784 KB Output is correct
18 Correct 20 ms 122716 KB Output is correct
19 Correct 19 ms 122708 KB Output is correct
20 Correct 19 ms 122704 KB Output is correct
21 Correct 19 ms 122716 KB Output is correct
22 Correct 19 ms 122712 KB Output is correct
23 Correct 19 ms 122512 KB Output is correct
24 Correct 19 ms 122716 KB Output is correct
25 Correct 19 ms 122708 KB Output is correct
26 Correct 19 ms 122716 KB Output is correct
27 Correct 19 ms 122672 KB Output is correct
28 Correct 19 ms 122716 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 122456 KB Output is correct
2 Correct 33 ms 122452 KB Output is correct
3 Correct 18 ms 122460 KB Output is correct
4 Correct 17 ms 122464 KB Output is correct
5 Correct 18 ms 122448 KB Output is correct
6 Correct 19 ms 122712 KB Output is correct
7 Correct 19 ms 122716 KB Output is correct
8 Correct 20 ms 122828 KB Output is correct
9 Correct 21 ms 122716 KB Output is correct
10 Correct 165 ms 146888 KB Output is correct
11 Correct 232 ms 155588 KB Output is correct
12 Correct 221 ms 153820 KB Output is correct
13 Correct 230 ms 156356 KB Output is correct
14 Correct 213 ms 160760 KB Output is correct
15 Correct 19 ms 122716 KB Output is correct
16 Correct 19 ms 122796 KB Output is correct
17 Correct 18 ms 122716 KB Output is correct
18 Correct 19 ms 122728 KB Output is correct
19 Correct 18 ms 122456 KB Output is correct
20 Correct 19 ms 122716 KB Output is correct
21 Correct 19 ms 122712 KB Output is correct
22 Correct 18 ms 122784 KB Output is correct
23 Correct 20 ms 122716 KB Output is correct
24 Correct 19 ms 122708 KB Output is correct
25 Correct 19 ms 122704 KB Output is correct
26 Correct 19 ms 122716 KB Output is correct
27 Correct 19 ms 122712 KB Output is correct
28 Correct 19 ms 122512 KB Output is correct
29 Correct 19 ms 122716 KB Output is correct
30 Correct 19 ms 122708 KB Output is correct
31 Correct 19 ms 122716 KB Output is correct
32 Correct 19 ms 122672 KB Output is correct
33 Correct 19 ms 122716 KB Output is correct
34 Correct 32 ms 124764 KB Output is correct
35 Correct 266 ms 154880 KB Output is correct
36 Correct 234 ms 148676 KB Output is correct
37 Correct 238 ms 144160 KB Output is correct
38 Correct 213 ms 142716 KB Output is correct
39 Correct 215 ms 141828 KB Output is correct
40 Correct 173 ms 139200 KB Output is correct
41 Correct 286 ms 150736 KB Output is correct
42 Correct 244 ms 153156 KB Output is correct
43 Correct 242 ms 156392 KB Output is correct
44 Correct 190 ms 140488 KB Output is correct
45 Correct 187 ms 142584 KB Output is correct
46 Correct 235 ms 146344 KB Output is correct
47 Correct 215 ms 142028 KB Output is correct
48 Correct 194 ms 141824 KB Output is correct
49 Correct 73 ms 135104 KB Output is correct
50 Correct 69 ms 132200 KB Output is correct
51 Correct 160 ms 139460 KB Output is correct
52 Correct 272 ms 152160 KB Output is correct
53 Correct 250 ms 147632 KB Output is correct
54 Correct 334 ms 159192 KB Output is correct
55 Correct 246 ms 159428 KB Output is correct
56 Correct 244 ms 147156 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 122452 KB Output is correct
2 Correct 18 ms 122460 KB Output is correct
3 Correct 17 ms 122464 KB Output is correct
4 Correct 18 ms 122448 KB Output is correct
5 Correct 19 ms 122712 KB Output is correct
6 Correct 19 ms 122716 KB Output is correct
7 Correct 20 ms 122828 KB Output is correct
8 Correct 21 ms 122716 KB Output is correct
9 Correct 165 ms 146888 KB Output is correct
10 Correct 232 ms 155588 KB Output is correct
11 Correct 221 ms 153820 KB Output is correct
12 Correct 230 ms 156356 KB Output is correct
13 Correct 213 ms 160760 KB Output is correct
14 Correct 200 ms 145864 KB Output is correct
15 Correct 507 ms 158976 KB Output is correct
16 Correct 541 ms 154240 KB Output is correct
17 Correct 519 ms 164372 KB Output is correct
18 Correct 508 ms 161156 KB Output is correct
19 Correct 476 ms 142856 KB Output is correct
20 Correct 465 ms 143660 KB Output is correct
21 Correct 504 ms 143424 KB Output is correct
22 Correct 485 ms 143660 KB Output is correct
23 Correct 477 ms 143412 KB Output is correct
24 Correct 492 ms 142724 KB Output is correct
25 Correct 530 ms 143304 KB Output is correct
26 Correct 537 ms 142664 KB Output is correct
27 Correct 19 ms 122716 KB Output is correct
28 Correct 19 ms 122796 KB Output is correct
29 Correct 18 ms 122716 KB Output is correct
30 Correct 19 ms 122728 KB Output is correct
31 Correct 18 ms 122456 KB Output is correct
32 Correct 19 ms 122716 KB Output is correct
33 Correct 19 ms 122712 KB Output is correct
34 Correct 18 ms 122784 KB Output is correct
35 Correct 20 ms 122716 KB Output is correct
36 Correct 32 ms 124764 KB Output is correct
37 Correct 266 ms 154880 KB Output is correct
38 Correct 234 ms 148676 KB Output is correct
39 Correct 238 ms 144160 KB Output is correct
40 Correct 213 ms 142716 KB Output is correct
41 Correct 215 ms 141828 KB Output is correct
42 Correct 173 ms 139200 KB Output is correct
43 Correct 286 ms 150736 KB Output is correct
44 Correct 244 ms 153156 KB Output is correct
45 Correct 242 ms 156392 KB Output is correct
46 Correct 190 ms 140488 KB Output is correct
47 Correct 53 ms 125172 KB Output is correct
48 Correct 589 ms 154416 KB Output is correct
49 Correct 635 ms 150768 KB Output is correct
50 Correct 594 ms 149292 KB Output is correct
51 Correct 725 ms 147960 KB Output is correct
52 Correct 543 ms 145728 KB Output is correct
53 Correct 397 ms 140220 KB Output is correct
54 Correct 637 ms 153504 KB Output is correct
55 Correct 619 ms 155832 KB Output is correct
56 Correct 632 ms 161984 KB Output is correct
57 Correct 554 ms 145968 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 122456 KB Output is correct
2 Correct 33 ms 122452 KB Output is correct
3 Correct 18 ms 122460 KB Output is correct
4 Correct 17 ms 122464 KB Output is correct
5 Correct 18 ms 122448 KB Output is correct
6 Correct 19 ms 122712 KB Output is correct
7 Correct 19 ms 122716 KB Output is correct
8 Correct 20 ms 122828 KB Output is correct
9 Correct 21 ms 122716 KB Output is correct
10 Correct 165 ms 146888 KB Output is correct
11 Correct 232 ms 155588 KB Output is correct
12 Correct 221 ms 153820 KB Output is correct
13 Correct 230 ms 156356 KB Output is correct
14 Correct 213 ms 160760 KB Output is correct
15 Correct 200 ms 145864 KB Output is correct
16 Correct 507 ms 158976 KB Output is correct
17 Correct 541 ms 154240 KB Output is correct
18 Correct 519 ms 164372 KB Output is correct
19 Correct 508 ms 161156 KB Output is correct
20 Correct 476 ms 142856 KB Output is correct
21 Correct 465 ms 143660 KB Output is correct
22 Correct 504 ms 143424 KB Output is correct
23 Correct 485 ms 143660 KB Output is correct
24 Correct 477 ms 143412 KB Output is correct
25 Correct 492 ms 142724 KB Output is correct
26 Correct 530 ms 143304 KB Output is correct
27 Correct 537 ms 142664 KB Output is correct
28 Correct 19 ms 122716 KB Output is correct
29 Correct 19 ms 122796 KB Output is correct
30 Correct 18 ms 122716 KB Output is correct
31 Correct 19 ms 122728 KB Output is correct
32 Correct 18 ms 122456 KB Output is correct
33 Correct 19 ms 122716 KB Output is correct
34 Correct 19 ms 122712 KB Output is correct
35 Correct 18 ms 122784 KB Output is correct
36 Correct 20 ms 122716 KB Output is correct
37 Correct 32 ms 124764 KB Output is correct
38 Correct 266 ms 154880 KB Output is correct
39 Correct 234 ms 148676 KB Output is correct
40 Correct 238 ms 144160 KB Output is correct
41 Correct 213 ms 142716 KB Output is correct
42 Correct 215 ms 141828 KB Output is correct
43 Correct 173 ms 139200 KB Output is correct
44 Correct 286 ms 150736 KB Output is correct
45 Correct 244 ms 153156 KB Output is correct
46 Correct 242 ms 156392 KB Output is correct
47 Correct 190 ms 140488 KB Output is correct
48 Correct 53 ms 125172 KB Output is correct
49 Correct 589 ms 154416 KB Output is correct
50 Correct 635 ms 150768 KB Output is correct
51 Correct 594 ms 149292 KB Output is correct
52 Correct 725 ms 147960 KB Output is correct
53 Correct 543 ms 145728 KB Output is correct
54 Correct 397 ms 140220 KB Output is correct
55 Correct 637 ms 153504 KB Output is correct
56 Correct 619 ms 155832 KB Output is correct
57 Correct 632 ms 161984 KB Output is correct
58 Correct 554 ms 145968 KB Output is correct
59 Correct 156 ms 133572 KB Output is correct
60 Correct 532 ms 157872 KB Output is correct
61 Correct 499 ms 154988 KB Output is correct
62 Correct 634 ms 159904 KB Output is correct
63 Correct 520 ms 161036 KB Output is correct
64 Correct 19 ms 122708 KB Output is correct
65 Correct 19 ms 122704 KB Output is correct
66 Correct 19 ms 122716 KB Output is correct
67 Correct 19 ms 122712 KB Output is correct
68 Correct 19 ms 122512 KB Output is correct
69 Correct 19 ms 122716 KB Output is correct
70 Correct 19 ms 122708 KB Output is correct
71 Correct 19 ms 122716 KB Output is correct
72 Correct 19 ms 122672 KB Output is correct
73 Correct 19 ms 122716 KB Output is correct
74 Correct 187 ms 142584 KB Output is correct
75 Correct 235 ms 146344 KB Output is correct
76 Correct 215 ms 142028 KB Output is correct
77 Correct 194 ms 141824 KB Output is correct
78 Correct 73 ms 135104 KB Output is correct
79 Correct 69 ms 132200 KB Output is correct
80 Correct 160 ms 139460 KB Output is correct
81 Correct 272 ms 152160 KB Output is correct
82 Correct 250 ms 147632 KB Output is correct
83 Correct 334 ms 159192 KB Output is correct
84 Correct 246 ms 159428 KB Output is correct
85 Correct 244 ms 147156 KB Output is correct
86 Correct 127 ms 130924 KB Output is correct
87 Correct 633 ms 150560 KB Output is correct
88 Correct 599 ms 151076 KB Output is correct
89 Correct 486 ms 145576 KB Output is correct
90 Correct 232 ms 138524 KB Output is correct
91 Correct 281 ms 139048 KB Output is correct
92 Correct 414 ms 144168 KB Output is correct
93 Correct 688 ms 156932 KB Output is correct
94 Correct 540 ms 152220 KB Output is correct
95 Correct 668 ms 162496 KB Output is correct
96 Correct 560 ms 157232 KB Output is correct
97 Correct 562 ms 148872 KB Output is correct