oj.uz

답안 #552690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552690 2022-04-23T15:33:45 Z Magi 자매 도시 (APIO20_swap) C++14
7 / 100
 559 ms 50676 KB 
#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];
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;

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

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

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

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

            else if(max(u.s, dp_jos[0][u.f].f) < dp_jos[1][x].f){
                dp_jos[1][x] = {max(u.s, dp_jos[0][u.f].f), 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;
        val2 = min(val2, minLant(x, val));

        val2 = min(val2, dp_sus[LCA.f]);

    }

    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]));


    }

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

Subtask #1
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 3 ms 5076 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5404 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 135 ms 37060 KB Output is correct
10 Correct 138 ms 45660 KB Output is correct
11 Correct 145 ms 44400 KB Output is correct
12 Correct 212 ms 46796 KB Output is correct
13 Correct 116 ms 48972 KB Output is correct
14 Correct 134 ms 36364 KB Output is correct
15 Correct 559 ms 47540 KB Output is correct
16 Correct 492 ms 44532 KB Output is correct
17 Correct 428 ms 50676 KB Output is correct
18 Correct 430 ms 49020 KB Output is correct
19 Incorrect 110 ms 14200 KB Output isn't correct
20 Halted 0 ms 0 KB -

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 186 ms 42636 KB Output is correct
4 Correct 188 ms 44116 KB Output is correct
5 Correct 197 ms 43392 KB Output is correct
6 Correct 193 ms 44032 KB Output is correct
7 Correct 202 ms 44024 KB Output is correct
8 Correct 247 ms 42380 KB Output is correct
9 Correct 188 ms 43752 KB Output is correct
10 Correct 195 ms 42104 KB Output is correct

Subtask #3
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 3 ms 5076 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5404 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Incorrect 3 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 3 ms 5076 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5404 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 135 ms 37060 KB Output is correct
10 Correct 138 ms 45660 KB Output is correct
11 Correct 145 ms 44400 KB Output is correct
12 Correct 212 ms 46796 KB Output is correct
13 Correct 116 ms 48972 KB Output is correct
14 Correct 134 ms 36364 KB Output is correct
15 Correct 559 ms 47540 KB Output is correct
16 Correct 492 ms 44532 KB Output is correct
17 Correct 428 ms 50676 KB Output is correct
18 Correct 430 ms 49020 KB Output is correct
19 Correct 186 ms 42636 KB Output is correct
20 Correct 188 ms 44116 KB Output is correct
21 Correct 197 ms 43392 KB Output is correct
22 Correct 193 ms 44032 KB Output is correct
23 Correct 202 ms 44024 KB Output is correct
24 Correct 247 ms 42380 KB Output is correct
25 Correct 188 ms 43752 KB Output is correct
26 Correct 195 ms 42104 KB Output is correct
27 Correct 4 ms 5428 KB Output is correct
28 Correct 4 ms 5408 KB Output is correct
29 Correct 4 ms 5460 KB Output is correct
30 Correct 4 ms 5460 KB Output is correct
31 Correct 4 ms 5408 KB Output is correct
32 Correct 4 ms 5460 KB Output is correct
33 Correct 4 ms 5460 KB Output is correct
34 Correct 5 ms 5468 KB Output is correct
35 Correct 5 ms 5424 KB Output is correct
36 Correct 16 ms 9796 KB Output is correct
37 Correct 140 ms 47084 KB Output is correct
38 Correct 141 ms 44040 KB Output is correct
39 Correct 167 ms 41708 KB Output is correct
40 Correct 137 ms 40984 KB Output is correct
41 Correct 150 ms 40472 KB Output is correct
42 Correct 114 ms 37940 KB Output is correct
43 Correct 183 ms 44840 KB Output is correct
44 Correct 146 ms 47024 KB Output is correct
45 Correct 121 ms 48448 KB Output is correct
46 Correct 162 ms 42532 KB Output is correct
47 Incorrect 38 ms 10028 KB Output isn't correct
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -