oj.uz

Submission #553139

# Submission time Handle Problem Language Result Execution time Memory
553139 2022-04-24T18:26:07 Z Itamar Swapping Cities (APIO20_swap) C++14
13 / 100
 297 ms 33320 KB 
#include "swap.h"

#include <cassert>
#include <cstdio>
#pragma warning(disable : 4996)
#include <map>
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define ll long long
#define vi vector<int> 
#define vll vector<ll>
#define pi pair<int,int> 
#define pll pair<ll,ll>


vi col_v;
vector<vector<pi>> his;
vector<vi> col;
vector<pi> kats;
void uni(int i, int j, int t) {
    if (col_v[i] == col_v[j]) {
        if (his[i][0].first == -1) {
            for (int x : col[col_v[i]]) {
                his[x][0] = { t,-1 };
            }
        }
        return;
    }
    if (col[col_v[i]].size() > col[col_v[j]].size())
        swap(i, j);
    int c = col_v[j];
    int c1 = col_v[i];
    if (his[i][0].first != -1) {
        if (his[j][0].first == -1) {
            for (int x : col[c]) {
                his[x][0] = { t,-1 };
            }
        }
    }
    else if (his[j][0].first != -1) {
        if (his[i][0].first == -1) {
            for (int x : col[c1]) {
                his[x][0] = { t,-1 };
            }
        }
    }
    else if (i == kats[c1].first) {
        if (j == kats[c].second) {
            kats[c] = { kats[c1].second,kats[c].first };
        }
        else if (j == kats[c].first) {
            kats[c] = { kats[c1].second,kats[c].second };
        }
        else {
            for (int x : col[c1]) {
                his[x][0] = { t,-1 };
            }
            for (int x : col[c]) {
                his[x][0] = { t,-1 };
            }
        }
    }
    else if (i == kats[c1].second) {
        if (j == kats[c].second) {
            kats[c] = { kats[c1].first,kats[c].first };
        }
        else if (j == kats[c].first) {
            kats[c] = { kats[c1].first,kats[c].second };
        }
        else {
            for (int x : col[c1]) {
                his[x][0] = { t,-1 };
            }
            for (int x : col[c]) {
                his[x][0] = { t,-1 };
            }
        }
    }
    else {
        for (int x : col[c1]) {
            his[x][0] = { t,-1 };
        }
        for (int x : col[c]) {
            his[x][0] = { t,-1 };
        }
    }

    for (int x : col[col_v[i]]) {
        col_v[x] = c;
        col[col_v[j]].push_back(x);
        his[x].push_back({ t,c });
    }
}
void init(int N, int M,
    std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    col_v.resize(N);
    his.resize(N);
    vector<vi> v;
    for (int i = 0; i < N; i++) {
        his[i].push_back({ -1,-1 });
        his[i].push_back({ 0,i });
        kats.push_back( { i, i });
    }

    col.resize(N);
    for (int i = 0; i < N; i++) {
        col_v[i] = i;
        col[i].push_back(i);
    }
    for (int i = 0; i < M; i++) {
        v.push_back({ W[i],V[i],U[i] });
    }
    sort(v.begin(), v.end());
    for (vi vec : v) {
        uni(vec[1], vec[2], vec[0]);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    
    vector<pi> v1 = his[X];
    vector<pi> v2 = his[Y];
    int s = max(v1[0].first, v2[0].first);
    int it1 = v1.size() - 1;
    int it2= v2.size() - 1;
    if (v1[0].first == -1)
        return -1;
    while (true) {
        it1--;
        it2--;
        if (v1[it1].second != v2[it2+1].second ) {
            return max(v1[it1+1].first, s);
        }
        if (v1[it1+1].second != v2[it2 ].second) {
            return max(v2[it2 + 1].first, s);
        }

    }

}

Compilation message

swap.cpp:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    5 | #pragma warning(disable : 4996)
      |

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 144 ms 24948 KB Output is correct
10 Correct 196 ms 30108 KB Output is correct
11 Correct 199 ms 29420 KB Output is correct
12 Correct 198 ms 31336 KB Output is correct
13 Correct 131 ms 23508 KB Output is correct
14 Correct 154 ms 25012 KB Output is correct
15 Correct 274 ms 32160 KB Output is correct
16 Correct 297 ms 31164 KB Output is correct
17 Correct 290 ms 33320 KB Output is correct
18 Correct 239 ms 25144 KB Output is correct
19 Correct 75 ms 7944 KB Output is correct
20 Correct 279 ms 32320 KB Output is correct
21 Correct 287 ms 31080 KB Output is correct
22 Correct 296 ms 33248 KB Output is correct
23 Correct 208 ms 25136 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 202 ms 23364 KB Output is correct
4 Correct 193 ms 24520 KB Output is correct
5 Correct 190 ms 23732 KB Output is correct
6 Correct 184 ms 24368 KB Output is correct
7 Correct 194 ms 24068 KB Output is correct
8 Correct 192 ms 23132 KB Output is correct
9 Correct 185 ms 23976 KB Output is correct
10 Correct 194 ms 22872 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 2 ms 468 KB Output isn't correct
11 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 0 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 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 144 ms 24948 KB Output is correct
11 Correct 196 ms 30108 KB Output is correct
12 Correct 199 ms 29420 KB Output is correct
13 Correct 198 ms 31336 KB Output is correct
14 Correct 131 ms 23508 KB Output is correct
15 Incorrect 2 ms 468 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 144 ms 24948 KB Output is correct
10 Correct 196 ms 30108 KB Output is correct
11 Correct 199 ms 29420 KB Output is correct
12 Correct 198 ms 31336 KB Output is correct
13 Correct 131 ms 23508 KB Output is correct
14 Correct 154 ms 25012 KB Output is correct
15 Correct 274 ms 32160 KB Output is correct
16 Correct 297 ms 31164 KB Output is correct
17 Correct 290 ms 33320 KB Output is correct
18 Correct 239 ms 25144 KB Output is correct
19 Correct 202 ms 23364 KB Output is correct
20 Correct 193 ms 24520 KB Output is correct
21 Correct 190 ms 23732 KB Output is correct
22 Correct 184 ms 24368 KB Output is correct
23 Correct 194 ms 24068 KB Output is correct
24 Correct 192 ms 23132 KB Output is correct
25 Correct 185 ms 23976 KB Output is correct
26 Correct 194 ms 22872 KB Output is correct
27 Incorrect 2 ms 468 KB Output isn't correct
28 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 0 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 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 144 ms 24948 KB Output is correct
11 Correct 196 ms 30108 KB Output is correct
12 Correct 199 ms 29420 KB Output is correct
13 Correct 198 ms 31336 KB Output is correct
14 Correct 131 ms 23508 KB Output is correct
15 Correct 154 ms 25012 KB Output is correct
16 Correct 274 ms 32160 KB Output is correct
17 Correct 297 ms 31164 KB Output is correct
18 Correct 290 ms 33320 KB Output is correct
19 Correct 239 ms 25144 KB Output is correct
20 Correct 202 ms 23364 KB Output is correct
21 Correct 193 ms 24520 KB Output is correct
22 Correct 190 ms 23732 KB Output is correct
23 Correct 184 ms 24368 KB Output is correct
24 Correct 194 ms 24068 KB Output is correct
25 Correct 192 ms 23132 KB Output is correct
26 Correct 185 ms 23976 KB Output is correct
27 Correct 194 ms 22872 KB Output is correct
28 Incorrect 2 ms 468 KB Output isn't correct
29 Halted 0 ms 0 KB -