oj.uz

Submission #551825

# Submission time Handle Problem Language Result Execution time Memory
551825 2022-04-21T16:34:19 Z nicolaalexandra Swapping Cities (APIO20_swap) C++14
13 / 100
 189 ms 29508 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define DIM 200010
#define INF 2000000000
using namespace std;

struct muchie{
    int x,y,cost;
} mch[DIM];

vector<pair <int,int> > L[DIM];
vector <int> a[DIM];
int t[DIM],ok[DIM],g[DIM],dp[DIM];
int n,m,subtask,maxi;

inline int cmp (muchie a, muchie b){
    return a.cost < b.cost;
}

inline int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

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

    n = N, m = M;
    for (int i=0;i<m;i++){
        int x = U[i], y = V[i], cost = W[i];
        x++, y++;

        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
        maxi = max (maxi,cost);

        mch[i+1] = {x,y,cost};
    }

    subtask = 1;
    for (int i=1;i<=n;i++)
        if (L[i].size() > 2)
            subtask = 0;

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

    for (int i=1;i<=n;i++){
        t[i] = dp[i] = -1;
        ok[i] = g[i] = 0;
        a[i].push_back(i);
    }

    for (int i=1;i<=m;i++){

        int x = mch[i].x, y = mch[i].y;
        int radx = get_rad(x), rady = get_rad(y);

        if (radx != rady){
            if (t[radx] > t[rady])
                swap (radx, rady);

            if (!ok[radx] && ok[rady]){
                for (auto it : a[radx])
                    dp[it] = mch[i].cost;
                ok[radx] = 1;
            }

            if (ok[radx] && !ok[rady]){
                for (auto it : a[rady])
                    dp[it] = mch[i].cost;
            }

            for (auto it : a[rady])
                a[radx].push_back(it);
            a[rady].clear();

            //ok[radx] |= ok[rady];
            t[radx] += t[rady];
            t[rady] = radx;

            g[x]++, g[y]++;
            if (g[x] >= 3 || g[y] >= 3){
                if (!ok[radx]){
                    ok[radx] = 1;
                    for (auto it : a[radx])
                        dp[it] = mch[i].cost;
                }
            }
        } else {
            /// o sa am un ciclu in componenta asta

            if (!ok[radx]){
                ok[radx] = 1;
                for (auto it : a[radx])
                    dp[it] = mch[i].cost;
            }
        }


        //if (get_rad(X) == get_rad(Y) && ok[get_rad(X)])
          //  return mch[i].cost;
    }


}


int getMinimumFuelCapacity(int X, int Y) {

    if (subtask == 1){
        if (m == n-1)
            return -1;
        else return maxi;
    }

    X++, Y++;

    if (dp[X] == -1 || dp[Y] == -1)
        return -1;
    else return max (dp[X],dp[Y]);
}
/*
int main (){

    FILE *fin = fopen ("date.in", "r");
    FILE *fout = fopen ("date.out", "w");

    int N, M;
    assert(2 == fscanf(fin, "%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == fscanf(fin, "%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == fscanf(fin,"%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == fscanf(fin,"%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        fprintf(fout, "%d\n", minimum_fuel_capacities[i]);
    }



    return 0;
}

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9868 KB Output is correct
6 Correct 6 ms 9852 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 75 ms 22280 KB Output is correct
10 Correct 83 ms 24676 KB Output is correct
11 Correct 99 ms 24388 KB Output is correct
12 Correct 98 ms 25248 KB Output is correct
13 Correct 97 ms 22492 KB Output is correct
14 Correct 79 ms 22480 KB Output is correct
15 Correct 151 ms 26620 KB Output is correct
16 Correct 134 ms 26348 KB Output is correct
17 Correct 150 ms 27116 KB Output is correct
18 Correct 160 ms 24124 KB Output is correct
19 Correct 62 ms 16084 KB Output is correct
20 Correct 189 ms 27572 KB Output is correct
21 Correct 150 ms 27424 KB Output is correct
22 Correct 163 ms 28460 KB Output is correct
23 Correct 146 ms 25516 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 136 ms 25744 KB Output is correct
4 Correct 127 ms 29424 KB Output is correct
5 Correct 130 ms 29440 KB Output is correct
6 Correct 137 ms 29276 KB Output is correct
7 Correct 126 ms 29508 KB Output is correct
8 Correct 131 ms 28860 KB Output is correct
9 Correct 132 ms 29252 KB Output is correct
10 Correct 125 ms 28764 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9868 KB Output is correct
6 Correct 6 ms 9852 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 5 ms 9636 KB Output is correct
10 Incorrect 6 ms 9812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 6 ms 9868 KB Output is correct
7 Correct 6 ms 9852 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 75 ms 22280 KB Output is correct
11 Correct 83 ms 24676 KB Output is correct
12 Correct 99 ms 24388 KB Output is correct
13 Correct 98 ms 25248 KB Output is correct
14 Correct 97 ms 22492 KB Output is correct
15 Incorrect 6 ms 9812 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 6 ms 9712 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9868 KB Output is correct
6 Correct 6 ms 9852 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 75 ms 22280 KB Output is correct
10 Correct 83 ms 24676 KB Output is correct
11 Correct 99 ms 24388 KB Output is correct
12 Correct 98 ms 25248 KB Output is correct
13 Correct 97 ms 22492 KB Output is correct
14 Correct 79 ms 22480 KB Output is correct
15 Correct 151 ms 26620 KB Output is correct
16 Correct 134 ms 26348 KB Output is correct
17 Correct 150 ms 27116 KB Output is correct
18 Correct 160 ms 24124 KB Output is correct
19 Correct 136 ms 25744 KB Output is correct
20 Correct 127 ms 29424 KB Output is correct
21 Correct 130 ms 29440 KB Output is correct
22 Correct 137 ms 29276 KB Output is correct
23 Correct 126 ms 29508 KB Output is correct
24 Correct 131 ms 28860 KB Output is correct
25 Correct 132 ms 29252 KB Output is correct
26 Correct 125 ms 28764 KB Output is correct
27 Incorrect 6 ms 9812 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 6 ms 9712 KB Output is correct
5 Correct 6 ms 9712 KB Output is correct
6 Correct 6 ms 9868 KB Output is correct
7 Correct 6 ms 9852 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 75 ms 22280 KB Output is correct
11 Correct 83 ms 24676 KB Output is correct
12 Correct 99 ms 24388 KB Output is correct
13 Correct 98 ms 25248 KB Output is correct
14 Correct 97 ms 22492 KB Output is correct
15 Correct 79 ms 22480 KB Output is correct
16 Correct 151 ms 26620 KB Output is correct
17 Correct 134 ms 26348 KB Output is correct
18 Correct 150 ms 27116 KB Output is correct
19 Correct 160 ms 24124 KB Output is correct
20 Correct 136 ms 25744 KB Output is correct
21 Correct 127 ms 29424 KB Output is correct
22 Correct 130 ms 29440 KB Output is correct
23 Correct 137 ms 29276 KB Output is correct
24 Correct 126 ms 29508 KB Output is correct
25 Correct 131 ms 28860 KB Output is correct
26 Correct 132 ms 29252 KB Output is correct
27 Correct 125 ms 28764 KB Output is correct
28 Incorrect 6 ms 9812 KB Output isn't correct
29 Halted 0 ms 0 KB -