답안 #552721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552721	2022-04-23T16:59:52 Z	Magi	자매 도시 (APIO20_swap)	C++14	100 / 100	683 ms	57124 KB

swap

#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second

using namespace std;

const int NMAX = 1e5, MMAX = 2e5, inf = 2e9;
int n, m, tata[NMAX+10], rang[NMAX+10], mini[3][NMAX+10], costTata[NMAX+10], dp[20][NMAX+10], dp1[20][NMAX+10], dp2[20][NMAX+10], nivel[NMAX+10];
int dp_sus[NMAX+10], dpCycle[NMAX+10];
pair <int, int> dp_jos[2][NMAX+10];

vector <pair <int, int> > nod[NMAX+10], tree[NMAX+10];

struct Kruskal{
    int n1, n2, cost;
}K[MMAX+10];

inline bool cmp(Kruskal a, Kruskal b){
    return a.cost < b.cost;
}

int findDaddy(int x){
    int r = x, y = x;
    while(r != tata[r])
        r = tata[r];
    while(x != tata[x]){
        y = tata[x];
        tata[x] = r;
        x = y;
    }
    return r;
}

void unite(int x, int y){

    if(rang[x] < rang[y])
        tata[x] = y;
    else
        tata[y] = x;
    if(rang[x] == rang[y])
        rang[x]++;
}

void dfs(int x, int p = 0){

    dp[0][x] = p;
    nivel[x] = nivel[p] + 1;

    for(auto u : nod[x])
        if(u.f != p){

            for(int t=0; t<3; t++)
                if(mini[t][x] > u.s){
                    for(int t1=2; t1>t; t1--)
                        mini[t1][x] = mini[t1-1][x];
                    mini[t][x] = u.s;
                    break;
                }
        }

    for(auto u : tree[x])
        if(u.f != p){
            dfs(u.f, x);
            costTata[u.f] = u.s;
        }
}

void dfs1(int x, int p = 0){

    dp_jos[0][x].f = dp_jos[0][x].s = dp_jos[1][x].f = dp_jos[1][x].s = inf;

    dpCycle[x] = inf;
    for(auto u : nod[x])
        if(dp[0][u.f] != x && dp[0][x] != u.f)
            dpCycle[x] = min(dpCycle[x], u.s);

    for(auto u : tree[x])
        if(u.f != p){
            dfs1(u.f, x);

            if(max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])) < dp_jos[0][x].f){
                dp_jos[1][x] = dp_jos[0][x];
                dp_jos[0][x] = {max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])), u.s};
            }

            else if(max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])) < dp_jos[1][x].f){
                dp_jos[1][x] = {max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])), u.s};
            }

            dpCycle[x] = min(dpCycle[x], max(u.s, dpCycle[u.f]));
        }
}

void dfs2(int x, int p = 0){

    dp_sus[x] = min(min(mini[2][x], max(mini[1][x], costTata[x])), max(costTata[x], dp_sus[dp[0][x]]));
    if(dp_jos[0][dp[0][x]].s == x)
        dp_sus[x] = min(dp_sus[x], max(costTata[x], dp_jos[1][dp[0][x]].f));
    else
        dp_sus[x] = min(dp_sus[x], max(costTata[x], dp_jos[0][dp[0][x]].f));

    for(auto u : tree[x])
        if(u.f != p)
            dfs2(u.f, x);
}

void buildStramosi(){

    for(int i=1; i<=n; i++){
        if(costTata[i] != mini[0][dp[0][i]])
            dp2[0][i] = mini[0][dp[0][i]];
        else
            dp2[0][i] = mini[1][dp[0][i]];

        dp1[0][i] = costTata[i];
    }

    for(int bit=1; (1<<bit)<=n; bit++)
        for(int i=1; i<=n; i++){
            dp[bit][i] = dp[bit-1][dp[bit-1][i]];
            dp1[bit][i] = max(dp1[bit-1][i], dp1[bit-1][dp[bit-1][i]]);
            dp2[bit][i] = min(dp2[bit-1][i], dp2[bit-1][dp[bit-1][i]]);
        }

}

pair <int, int> lca(int x, int y){

    if(nivel[x] < nivel[y])
        swap(x, y);
    int dif = nivel[x] - nivel[y], ans = 0;

    for(int bit=0; (1<<bit)<=dif; bit++)
        if(dif & (1 << bit)){
            ans = max(ans, dp1[bit][x]);
            x = dp[bit][x];
        }

    if(x == y)
        return {x, ans};
    for(int bit=19; bit>=0; bit--)
        if(dp[bit][x] != dp[bit][y]){
            ans = max(ans, max(dp1[bit][x], dp1[bit][y]));
            x = dp[bit][x];
            y = dp[bit][y];
        }

    return {dp[0][x], max(ans, max(dp1[0][x], dp1[0][y]))};

}

int findStr(int x, int k){
    for(int bit=0; (1<<bit)<=k; bit++)
        if(k & (1 << bit))
            x = dp[bit][x];
    return x;
}

int minLant(int x, int k){
    int ans = inf;
    for(int bit=0; (1<<bit)<=k; bit++)
        if(k & (1 << bit)){
            ans = min(ans, dp2[bit][x]);
            x = dp[bit][x];
        }
    return ans;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W){

    n = N;
    m = M;

    for(int i=1; i<=n; i++)
        tata[i] = i, rang[i] = 1;

    for(int i=0; i<m; i++){
        int nod1 = U[i] + 1, nod2 = V[i] + 1, cost = W[i];
        nod[nod1].push_back({nod2, cost});
        nod[nod2].push_back({nod1, cost});

        K[i+1] = {nod1, nod2, cost};
    }

    sort(K+1, K+m+1, cmp);

    for(int i=1; i<=m; i++){
        int val1 = findDaddy(K[i].n1), val2 = findDaddy(K[i].n2);
        if(val1 != val2){
            unite(val1, val2);
            tree[K[i].n1].push_back({K[i].n2, K[i].cost});
            tree[K[i].n2].push_back({K[i].n1, K[i].cost});
        }
    }

    for(int i=1; i<=n; i++)
        mini[0][i] = mini[1][i] = mini[2][i] = inf;

    costTata[1] = inf;
    dfs(1);
    dfs1(1);
    dfs2(1);

    buildStramosi();

}

int getMinimumFuelCapacity(int X, int Y){

    int x = X + 1, y = Y + 1;
    pair <int, int> LCA = lca(x, y);
    int val1 = LCA.s, val2 = inf;

    if(findStr(y, nivel[y] - nivel[LCA.f]) == x)
        swap(x, y);

    if(findStr(x, nivel[x] - nivel[LCA.f]) == y){
        val2 = mini[1][x];

        int val = nivel[x] - nivel[LCA.f] - 1, str = findStr(x, val);
        val2 = min(val2, minLant(x, val));

        val2 = min(val2, dp_sus[str]);

        val2 = min(val2, dpCycle[y]);

    }

    else{
        val2 = min(dp_jos[0][x].f, dp_jos[0][y].f);
        val2 = min(val2, min(mini[1][x], mini[1][y]));

        int val = nivel[x] - nivel[LCA.f] - 1;
        val2 = min(val2, minLant(x, val));
        val = nivel[y] - nivel[LCA.f] - 1;
        val2 = min(val2, minLant(y, val));

        val2 = min(val2, min(mini[2][LCA.f], costTata[LCA.f]));

        val2 = min(val2, dpCycle[x]);
        val2 = min(val2, dpCycle[y]);
    }

    if(val2 == inf)
        return -1;
    return max(val1, val2);
}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	4 ms	5076 KB	Output is correct
4	Correct	4 ms	5332 KB	Output is correct
5	Correct	4 ms	5460 KB	Output is correct
6	Correct	4 ms	5460 KB	Output is correct
7	Correct	4 ms	5412 KB	Output is correct
8	Correct	4 ms	5460 KB	Output is correct
9	Correct	117 ms	36804 KB	Output is correct
10	Correct	212 ms	45172 KB	Output is correct
11	Correct	147 ms	43908 KB	Output is correct
12	Correct	162 ms	46180 KB	Output is correct
13	Correct	134 ms	47988 KB	Output is correct
14	Correct	179 ms	36320 KB	Output is correct
15	Correct	600 ms	46816 KB	Output is correct
16	Correct	558 ms	44216 KB	Output is correct
17	Correct	468 ms	49732 KB	Output is correct
18	Correct	550 ms	48376 KB	Output is correct
19	Correct	132 ms	15372 KB	Output is correct
20	Correct	560 ms	47360 KB	Output is correct
21	Correct	604 ms	45188 KB	Output is correct
22	Correct	518 ms	48728 KB	Output is correct
23	Correct	489 ms	49188 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	214 ms	43204 KB	Output is correct
4	Correct	211 ms	44700 KB	Output is correct
5	Correct	201 ms	43944 KB	Output is correct
6	Correct	208 ms	44648 KB	Output is correct
7	Correct	202 ms	44456 KB	Output is correct
8	Correct	226 ms	42924 KB	Output is correct
9	Correct	276 ms	44136 KB	Output is correct
10	Correct	207 ms	42620 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	4 ms	5076 KB	Output is correct
4	Correct	4 ms	5332 KB	Output is correct
5	Correct	4 ms	5460 KB	Output is correct
6	Correct	4 ms	5460 KB	Output is correct
7	Correct	4 ms	5412 KB	Output is correct
8	Correct	4 ms	5460 KB	Output is correct
9	Correct	4 ms	5020 KB	Output is correct
10	Correct	4 ms	5460 KB	Output is correct
11	Correct	4 ms	5408 KB	Output is correct
12	Correct	4 ms	5408 KB	Output is correct
13	Correct	3 ms	5460 KB	Output is correct
14	Correct	4 ms	5412 KB	Output is correct
15	Correct	4 ms	5416 KB	Output is correct
16	Correct	3 ms	5408 KB	Output is correct
17	Correct	4 ms	5460 KB	Output is correct
18	Correct	4 ms	5460 KB	Output is correct
19	Correct	5 ms	5332 KB	Output is correct
20	Correct	5 ms	5444 KB	Output is correct
21	Correct	4 ms	5408 KB	Output is correct
22	Correct	4 ms	5288 KB	Output is correct
23	Correct	4 ms	5460 KB	Output is correct
24	Correct	5 ms	5460 KB	Output is correct
25	Correct	4 ms	5540 KB	Output is correct
26	Correct	4 ms	5532 KB	Output is correct
27	Correct	4 ms	5460 KB	Output is correct
28	Correct	4 ms	5540 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5020 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	3 ms	5076 KB	Output is correct
4	Correct	4 ms	5076 KB	Output is correct
5	Correct	4 ms	5332 KB	Output is correct
6	Correct	4 ms	5460 KB	Output is correct
7	Correct	4 ms	5460 KB	Output is correct
8	Correct	4 ms	5412 KB	Output is correct
9	Correct	4 ms	5460 KB	Output is correct
10	Correct	117 ms	36804 KB	Output is correct
11	Correct	212 ms	45172 KB	Output is correct
12	Correct	147 ms	43908 KB	Output is correct
13	Correct	162 ms	46180 KB	Output is correct
14	Correct	134 ms	47988 KB	Output is correct
15	Correct	4 ms	5460 KB	Output is correct
16	Correct	4 ms	5408 KB	Output is correct
17	Correct	4 ms	5408 KB	Output is correct
18	Correct	3 ms	5460 KB	Output is correct
19	Correct	4 ms	5412 KB	Output is correct
20	Correct	4 ms	5416 KB	Output is correct
21	Correct	3 ms	5408 KB	Output is correct
22	Correct	4 ms	5460 KB	Output is correct
23	Correct	4 ms	5460 KB	Output is correct
24	Correct	5 ms	5332 KB	Output is correct
25	Correct	5 ms	5444 KB	Output is correct
26	Correct	4 ms	5408 KB	Output is correct
27	Correct	4 ms	5288 KB	Output is correct
28	Correct	4 ms	5460 KB	Output is correct
29	Correct	5 ms	5460 KB	Output is correct
30	Correct	4 ms	5540 KB	Output is correct
31	Correct	4 ms	5532 KB	Output is correct
32	Correct	4 ms	5460 KB	Output is correct
33	Correct	4 ms	5540 KB	Output is correct
34	Correct	16 ms	9816 KB	Output is correct
35	Correct	174 ms	46116 KB	Output is correct
36	Correct	149 ms	43532 KB	Output is correct
37	Correct	153 ms	41636 KB	Output is correct
38	Correct	179 ms	41004 KB	Output is correct
39	Correct	151 ms	40524 KB	Output is correct
40	Correct	140 ms	37832 KB	Output is correct
41	Correct	190 ms	44552 KB	Output is correct
42	Correct	175 ms	44748 KB	Output is correct
43	Correct	120 ms	46072 KB	Output is correct
44	Correct	154 ms	41136 KB	Output is correct
45	Correct	178 ms	40384 KB	Output is correct
46	Correct	149 ms	43436 KB	Output is correct
47	Correct	160 ms	41800 KB	Output is correct
48	Correct	182 ms	42312 KB	Output is correct
49	Correct	71 ms	18632 KB	Output is correct
50	Correct	66 ms	16716 KB	Output is correct
51	Correct	153 ms	33612 KB	Output is correct
52	Correct	198 ms	48840 KB	Output is correct
53	Correct	215 ms	49464 KB	Output is correct
54	Correct	269 ms	53408 KB	Output is correct
55	Correct	136 ms	48956 KB	Output is correct
56	Correct	226 ms	48484 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	4 ms	5076 KB	Output is correct
4	Correct	4 ms	5332 KB	Output is correct
5	Correct	4 ms	5460 KB	Output is correct
6	Correct	4 ms	5460 KB	Output is correct
7	Correct	4 ms	5412 KB	Output is correct
8	Correct	4 ms	5460 KB	Output is correct
9	Correct	117 ms	36804 KB	Output is correct
10	Correct	212 ms	45172 KB	Output is correct
11	Correct	147 ms	43908 KB	Output is correct
12	Correct	162 ms	46180 KB	Output is correct
13	Correct	134 ms	47988 KB	Output is correct
14	Correct	179 ms	36320 KB	Output is correct
15	Correct	600 ms	46816 KB	Output is correct
16	Correct	558 ms	44216 KB	Output is correct
17	Correct	468 ms	49732 KB	Output is correct
18	Correct	550 ms	48376 KB	Output is correct
19	Correct	214 ms	43204 KB	Output is correct
20	Correct	211 ms	44700 KB	Output is correct
21	Correct	201 ms	43944 KB	Output is correct
22	Correct	208 ms	44648 KB	Output is correct
23	Correct	202 ms	44456 KB	Output is correct
24	Correct	226 ms	42924 KB	Output is correct
25	Correct	276 ms	44136 KB	Output is correct
26	Correct	207 ms	42620 KB	Output is correct
27	Correct	4 ms	5460 KB	Output is correct
28	Correct	4 ms	5408 KB	Output is correct
29	Correct	4 ms	5408 KB	Output is correct
30	Correct	3 ms	5460 KB	Output is correct
31	Correct	4 ms	5412 KB	Output is correct
32	Correct	4 ms	5416 KB	Output is correct
33	Correct	3 ms	5408 KB	Output is correct
34	Correct	4 ms	5460 KB	Output is correct
35	Correct	4 ms	5460 KB	Output is correct
36	Correct	16 ms	9816 KB	Output is correct
37	Correct	174 ms	46116 KB	Output is correct
38	Correct	149 ms	43532 KB	Output is correct
39	Correct	153 ms	41636 KB	Output is correct
40	Correct	179 ms	41004 KB	Output is correct
41	Correct	151 ms	40524 KB	Output is correct
42	Correct	140 ms	37832 KB	Output is correct
43	Correct	190 ms	44552 KB	Output is correct
44	Correct	175 ms	44748 KB	Output is correct
45	Correct	120 ms	46072 KB	Output is correct
46	Correct	154 ms	41136 KB	Output is correct
47	Correct	51 ms	9804 KB	Output is correct
48	Correct	527 ms	46224 KB	Output is correct
49	Correct	548 ms	44764 KB	Output is correct
50	Correct	559 ms	43660 KB	Output is correct
51	Correct	526 ms	43260 KB	Output is correct
52	Correct	500 ms	40896 KB	Output is correct
53	Correct	282 ms	32884 KB	Output is correct
54	Correct	629 ms	46172 KB	Output is correct
55	Correct	608 ms	46744 KB	Output is correct
56	Correct	509 ms	49284 KB	Output is correct
57	Correct	430 ms	44340 KB	Output is correct

Subtask #6

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5020 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	3 ms	5076 KB	Output is correct
4	Correct	4 ms	5076 KB	Output is correct
5	Correct	4 ms	5332 KB	Output is correct
6	Correct	4 ms	5460 KB	Output is correct
7	Correct	4 ms	5460 KB	Output is correct
8	Correct	4 ms	5412 KB	Output is correct
9	Correct	4 ms	5460 KB	Output is correct
10	Correct	117 ms	36804 KB	Output is correct
11	Correct	212 ms	45172 KB	Output is correct
12	Correct	147 ms	43908 KB	Output is correct
13	Correct	162 ms	46180 KB	Output is correct
14	Correct	134 ms	47988 KB	Output is correct
15	Correct	179 ms	36320 KB	Output is correct
16	Correct	600 ms	46816 KB	Output is correct
17	Correct	558 ms	44216 KB	Output is correct
18	Correct	468 ms	49732 KB	Output is correct
19	Correct	550 ms	48376 KB	Output is correct
20	Correct	214 ms	43204 KB	Output is correct
21	Correct	211 ms	44700 KB	Output is correct
22	Correct	201 ms	43944 KB	Output is correct
23	Correct	208 ms	44648 KB	Output is correct
24	Correct	202 ms	44456 KB	Output is correct
25	Correct	226 ms	42924 KB	Output is correct
26	Correct	276 ms	44136 KB	Output is correct
27	Correct	207 ms	42620 KB	Output is correct
28	Correct	4 ms	5460 KB	Output is correct
29	Correct	4 ms	5408 KB	Output is correct
30	Correct	4 ms	5408 KB	Output is correct
31	Correct	3 ms	5460 KB	Output is correct
32	Correct	4 ms	5412 KB	Output is correct
33	Correct	4 ms	5416 KB	Output is correct
34	Correct	3 ms	5408 KB	Output is correct
35	Correct	4 ms	5460 KB	Output is correct
36	Correct	4 ms	5460 KB	Output is correct
37	Correct	16 ms	9816 KB	Output is correct
38	Correct	174 ms	46116 KB	Output is correct
39	Correct	149 ms	43532 KB	Output is correct
40	Correct	153 ms	41636 KB	Output is correct
41	Correct	179 ms	41004 KB	Output is correct
42	Correct	151 ms	40524 KB	Output is correct
43	Correct	140 ms	37832 KB	Output is correct
44	Correct	190 ms	44552 KB	Output is correct
45	Correct	175 ms	44748 KB	Output is correct
46	Correct	120 ms	46072 KB	Output is correct
47	Correct	154 ms	41136 KB	Output is correct
48	Correct	51 ms	9804 KB	Output is correct
49	Correct	527 ms	46224 KB	Output is correct
50	Correct	548 ms	44764 KB	Output is correct
51	Correct	559 ms	43660 KB	Output is correct
52	Correct	526 ms	43260 KB	Output is correct
53	Correct	500 ms	40896 KB	Output is correct
54	Correct	282 ms	32884 KB	Output is correct
55	Correct	629 ms	46172 KB	Output is correct
56	Correct	608 ms	46744 KB	Output is correct
57	Correct	509 ms	49284 KB	Output is correct
58	Correct	430 ms	44340 KB	Output is correct
59	Correct	132 ms	15372 KB	Output is correct
60	Correct	560 ms	47360 KB	Output is correct
61	Correct	604 ms	45188 KB	Output is correct
62	Correct	518 ms	48728 KB	Output is correct
63	Correct	489 ms	49188 KB	Output is correct
64	Correct	5 ms	5332 KB	Output is correct
65	Correct	5 ms	5444 KB	Output is correct
66	Correct	4 ms	5408 KB	Output is correct
67	Correct	4 ms	5288 KB	Output is correct
68	Correct	4 ms	5460 KB	Output is correct
69	Correct	5 ms	5460 KB	Output is correct
70	Correct	4 ms	5540 KB	Output is correct
71	Correct	4 ms	5532 KB	Output is correct
72	Correct	4 ms	5460 KB	Output is correct
73	Correct	4 ms	5540 KB	Output is correct
74	Correct	178 ms	40384 KB	Output is correct
75	Correct	149 ms	43436 KB	Output is correct
76	Correct	160 ms	41800 KB	Output is correct
77	Correct	182 ms	42312 KB	Output is correct
78	Correct	71 ms	18632 KB	Output is correct
79	Correct	66 ms	16716 KB	Output is correct
80	Correct	153 ms	33612 KB	Output is correct
81	Correct	198 ms	48840 KB	Output is correct
82	Correct	215 ms	49464 KB	Output is correct
83	Correct	269 ms	53408 KB	Output is correct
84	Correct	136 ms	48956 KB	Output is correct
85	Correct	226 ms	48484 KB	Output is correct
86	Correct	90 ms	18820 KB	Output is correct
87	Correct	549 ms	48036 KB	Output is correct
88	Correct	571 ms	48468 KB	Output is correct
89	Correct	390 ms	44848 KB	Output is correct
90	Correct	176 ms	22276 KB	Output is correct
91	Correct	199 ms	23944 KB	Output is correct
92	Correct	344 ms	38440 KB	Output is correct
93	Correct	555 ms	53884 KB	Output is correct
94	Correct	479 ms	53840 KB	Output is correct
95	Correct	683 ms	57124 KB	Output is correct
96	Correct	531 ms	51160 KB	Output is correct
97	Correct	416 ms	50668 KB	Output is correct