oj.uz

Submission #597739

# Submission time Handle Problem Language Result Execution time Memory
597739 2022-07-16T18:51:19 Z Ozy Swapping Cities (APIO20_swap) C++17
13 / 100
 147 ms 18072 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define w first
#define u second.first
#define v second.second

struct x{
    lli padre;
    lli flag;
    lli prof;
    lli val;
    lli l;
    lli r;
};

lli dis[MAX+2];
lli n,m,a,b,res;
vector< pair<lli, pair<lli,lli> > >  orden;
x uf[MAX+2];

lli dfs(lli pos) {
    if (dis[pos] > 0) return dis[pos]+1;
    if (uf[pos].padre == pos) {
        dis[pos] = 1;
        return 2;
    }
    dis[pos] = dfs(uf[pos].padre);
    return dis[pos]+1;
}

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

    rep(i,0,m-1) orden.push_back({W[i], {U[i]+1,V[i]+1} });
    sort(orden.begin(), orden.end());

    rep(i,1,n) uf[i] = {i,0,1,0,i,i};

    for (auto act : orden) {

        a = uf[act.u].padre;
        while (a != uf[a].padre) a = uf[a].padre;
        b = uf[act.v].padre;
        while (b != uf[b].padre) b = uf[b].padre;

        if (a == b) {
            if (uf[a].flag) continue;
            uf[a].flag = act.w;
        }
        else {

            if (uf[b].prof > uf[a].prof) {
                swap(a,b);
                swap(act.u, act.v);
            }

            uf[b].val = act.w;
            uf[b].padre = a;
            if (uf[b].prof == uf[a].prof) uf[a].prof++;

            if (uf[a].flag) continue;

            if (uf[b].flag) uf[a].flag = act.w;
            else {

                if (uf[a].l == act.u && uf[b].l == act.v) uf[a].l = uf[b].r;
                else if (uf[a].l == act.u && uf[b].r == act.v) uf[a].l = uf[b].l;
                else if (uf[a].r == act.u && uf[b].l == act.v) uf[a].r = uf[b].r;
                else if (uf[a].r == act.u && uf[b].r == act.v) uf[a].r = uf[b].l;
                else {
                     uf[a].flag = act.w;
                }

            }


        }

    }

    rep(i,1,n) if (dis[i] == 0) dis[i] = dfs(i);
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;

    if (dis[X] < dis[Y]) swap(X,Y);
    a = dis[X] - dis[Y];

    res = -1;
    rep(i,1,a) {
        res = max(res,uf[X].val);
        X = uf[X].padre;
    }

    while (X != Y) {
        res = max(res,uf[X].val);
        X = uf[X].padre;
        res = max(res,uf[Y].val);
        Y = uf[Y].padre;
    }

    while (uf[X].flag == 0) {
        res = max(res,uf[X].val);
        if (X != uf[X].padre) X = uf[X].padre;
        else return -1;
    }

    res = max(res,uf[X].flag);
    return res;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 47 ms 10040 KB Output is correct
10 Correct 45 ms 12220 KB Output is correct
11 Correct 49 ms 11988 KB Output is correct
12 Correct 53 ms 12716 KB Output is correct
13 Correct 49 ms 12724 KB Output is correct
14 Correct 44 ms 10428 KB Output is correct
15 Correct 118 ms 16272 KB Output is correct
16 Correct 117 ms 15888 KB Output is correct
17 Correct 140 ms 16704 KB Output is correct
18 Correct 101 ms 16652 KB Output is correct
19 Correct 60 ms 7484 KB Output is correct
20 Correct 116 ms 17304 KB Output is correct
21 Correct 147 ms 17292 KB Output is correct
22 Correct 126 ms 18000 KB Output is correct
23 Correct 111 ms 18072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 101 ms 13104 KB Output is correct
4 Correct 92 ms 13248 KB Output is correct
5 Correct 101 ms 13268 KB Output is correct
6 Correct 93 ms 13100 KB Output is correct
7 Correct 104 ms 13344 KB Output is correct
8 Correct 115 ms 12900 KB Output is correct
9 Correct 116 ms 13160 KB Output is correct
10 Correct 92 ms 12868 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Incorrect 1 ms 452 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 47 ms 10040 KB Output is correct
11 Correct 45 ms 12220 KB Output is correct
12 Correct 49 ms 11988 KB Output is correct
13 Correct 53 ms 12716 KB Output is correct
14 Correct 49 ms 12724 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Incorrect 1 ms 452 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 47 ms 10040 KB Output is correct
10 Correct 45 ms 12220 KB Output is correct
11 Correct 49 ms 11988 KB Output is correct
12 Correct 53 ms 12716 KB Output is correct
13 Correct 49 ms 12724 KB Output is correct
14 Correct 44 ms 10428 KB Output is correct
15 Correct 118 ms 16272 KB Output is correct
16 Correct 117 ms 15888 KB Output is correct
17 Correct 140 ms 16704 KB Output is correct
18 Correct 101 ms 16652 KB Output is correct
19 Correct 101 ms 13104 KB Output is correct
20 Correct 92 ms 13248 KB Output is correct
21 Correct 101 ms 13268 KB Output is correct
22 Correct 93 ms 13100 KB Output is correct
23 Correct 104 ms 13344 KB Output is correct
24 Correct 115 ms 12900 KB Output is correct
25 Correct 116 ms 13160 KB Output is correct
26 Correct 92 ms 12868 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 320 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 7 ms 2000 KB Output is correct
37 Correct 45 ms 12340 KB Output is correct
38 Incorrect 51 ms 12324 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 47 ms 10040 KB Output is correct
11 Correct 45 ms 12220 KB Output is correct
12 Correct 49 ms 11988 KB Output is correct
13 Correct 53 ms 12716 KB Output is correct
14 Correct 49 ms 12724 KB Output is correct
15 Correct 44 ms 10428 KB Output is correct
16 Correct 118 ms 16272 KB Output is correct
17 Correct 117 ms 15888 KB Output is correct
18 Correct 140 ms 16704 KB Output is correct
19 Correct 101 ms 16652 KB Output is correct
20 Correct 101 ms 13104 KB Output is correct
21 Correct 92 ms 13248 KB Output is correct
22 Correct 101 ms 13268 KB Output is correct
23 Correct 93 ms 13100 KB Output is correct
24 Correct 104 ms 13344 KB Output is correct
25 Correct 115 ms 12900 KB Output is correct
26 Correct 116 ms 13160 KB Output is correct
27 Correct 92 ms 12868 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 320 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 7 ms 2000 KB Output is correct
38 Correct 45 ms 12340 KB Output is correct
39 Incorrect 51 ms 12324 KB Output isn't correct
40 Halted 0 ms 0 KB -