oj.uz

Submission #672628

# Submission time Handle Problem Language Result Execution time Memory
672628 2022-12-17T04:08:10 Z Hanksburger Swapping Cities (APIO20_swap) C++17
13 / 100
 115 ms 13532 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int deg[100005], par[100005], sz[100005], w1[100005], w2[100005];
vector<pair<int, pair<int, int> > > edge;
int findPar(int x)
{
    return (par[x]==x)?x:findPar(par[x]);
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
//    cout << "init\n";
    for (int i=0; i<m; i++)
        edge.push_back({w[i], {u[i], v[i]}});
    sort(edge.begin(), edge.end());
    for (int i=0; i<n; i++)
    {
        par[i]=i;
        sz[i]=1;
        w1[i]=w2[i]=2e9;
    }
    for (int i=0; i<m; i++)
    {
        int x=edge[i].second.first, y=edge[i].second.second, z=edge[i].first;
        bool bridge=(deg[x]>=2 || deg[y]>=2);
        deg[x]++;
        deg[y]++;
        x=findPar(x);
        y=findPar(y);
        if (x==y)
        {
            w2[y]=min(w2[y], z);
            continue;
        }
        if (sz[x]>sz[y])
            swap(x, y);
        par[x]=y;
//        cout << "par[" << x << "]=" << y << '\n';
        sz[y]+=sz[x];
        w1[x]=z;
        if (bridge)
            w2[y]=min(w2[y], z);
    }
//    cout << "initend\n";
}
int getMinimumFuelCapacity(int x, int y)
{
    int ans=0;
    while (x!=y)
    {
//        cout << "x y " << x << ' ' << y << '\n';
//        cout << "w1[x] w1[y] " << w1[x] << ' ' << w1[y] << '\n';
        if (w1[x]<w1[y])
        {
            ans=w1[x];
            x=par[x];
        }
        else
        {
            ans=w1[y];
            y=par[y];
        }
    }
    while (par[x]!=x)
    {
        if (w2[x]<2e9)
            return max(ans, w2[x]);
        ans=w1[x];
        x=par[x];
    }
    if (w2[x]<2e9)
        return max(ans, w2[x]);
    return -1;
}

Subtask #1
6.0 / 6.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 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 328 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 320 KB Output is correct
9 Correct 34 ms 6324 KB Output is correct
10 Correct 42 ms 7744 KB Output is correct
11 Correct 42 ms 7544 KB Output is correct
12 Correct 43 ms 7992 KB Output is correct
13 Correct 41 ms 7992 KB Output is correct
14 Correct 39 ms 6720 KB Output is correct
15 Correct 111 ms 11932 KB Output is correct
16 Correct 107 ms 11648 KB Output is correct
17 Correct 113 ms 12032 KB Output is correct
18 Correct 96 ms 12064 KB Output is correct
19 Correct 64 ms 6804 KB Output is correct
20 Correct 108 ms 12704 KB Output is correct
21 Correct 113 ms 13052 KB Output is correct
22 Correct 115 ms 13532 KB Output is correct
23 Correct 99 ms 13456 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 1 ms 212 KB Output is correct
3 Correct 90 ms 12300 KB Output is correct
4 Correct 89 ms 12480 KB Output is correct
5 Correct 93 ms 12856 KB Output is correct
6 Correct 89 ms 12324 KB Output is correct
7 Correct 93 ms 12696 KB Output is correct
8 Correct 91 ms 12292 KB Output is correct
9 Correct 90 ms 12516 KB Output is correct
10 Correct 89 ms 12324 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 328 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 320 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 328 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 320 KB Output is correct
10 Correct 34 ms 6324 KB Output is correct
11 Correct 42 ms 7744 KB Output is correct
12 Correct 42 ms 7544 KB Output is correct
13 Correct 43 ms 7992 KB Output is correct
14 Correct 41 ms 7992 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 328 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 320 KB Output is correct
9 Correct 34 ms 6324 KB Output is correct
10 Correct 42 ms 7744 KB Output is correct
11 Correct 42 ms 7544 KB Output is correct
12 Correct 43 ms 7992 KB Output is correct
13 Correct 41 ms 7992 KB Output is correct
14 Correct 39 ms 6720 KB Output is correct
15 Correct 111 ms 11932 KB Output is correct
16 Correct 107 ms 11648 KB Output is correct
17 Correct 113 ms 12032 KB Output is correct
18 Correct 96 ms 12064 KB Output is correct
19 Correct 90 ms 12300 KB Output is correct
20 Correct 89 ms 12480 KB Output is correct
21 Correct 93 ms 12856 KB Output is correct
22 Correct 89 ms 12324 KB Output is correct
23 Correct 93 ms 12696 KB Output is correct
24 Correct 91 ms 12292 KB Output is correct
25 Correct 90 ms 12516 KB Output is correct
26 Correct 89 ms 12324 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 328 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 320 KB Output is correct
10 Correct 34 ms 6324 KB Output is correct
11 Correct 42 ms 7744 KB Output is correct
12 Correct 42 ms 7544 KB Output is correct
13 Correct 43 ms 7992 KB Output is correct
14 Correct 41 ms 7992 KB Output is correct
15 Correct 39 ms 6720 KB Output is correct
16 Correct 111 ms 11932 KB Output is correct
17 Correct 107 ms 11648 KB Output is correct
18 Correct 113 ms 12032 KB Output is correct
19 Correct 96 ms 12064 KB Output is correct
20 Correct 90 ms 12300 KB Output is correct
21 Correct 89 ms 12480 KB Output is correct
22 Correct 93 ms 12856 KB Output is correct
23 Correct 89 ms 12324 KB Output is correct
24 Correct 93 ms 12696 KB Output is correct
25 Correct 91 ms 12292 KB Output is correct
26 Correct 90 ms 12516 KB Output is correct
27 Correct 89 ms 12324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -