oj.uz

Submission #553145

# Submission time Handle Problem Language Result Execution time Memory
553145 2022-04-24T18:56:05 Z Itamar Swapping Cities (APIO20_swap) C++14
50 / 100
 485 ms 39512 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;
    vector<vi> vec;
    for (int i = 1; i <= it1; i++) {
        vec.push_back({ v1[i].first,v1[i].second,1});
    }
    for (int i = 1; i <= it2; i++) {
        vec.push_back({ v2[i].first,v2[i].second,2 });
    }
    sort(vec.begin(), vec.end());
    int l1=-1, l2=-1;

    for (int i = 0; i < vec.size(); i++) {
        int now = vec[i][0];
        if (vec[i][2] == 1) {
            l1 = vec[i][1];
        }
        else {
            l2 = vec[i][1];
        }
        if (l1 == l2 ) {
            return max(now,s);
        }
    }
    return s;
}

Compilation message

swap.cpp:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    5 | #pragma warning(disable : 4996)
      | 
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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 0 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 137 ms 24956 KB Output is correct
10 Correct 179 ms 30352 KB Output is correct
11 Correct 200 ms 29416 KB Output is correct
12 Correct 236 ms 31372 KB Output is correct
13 Correct 117 ms 23588 KB Output is correct
14 Correct 164 ms 24964 KB Output is correct
15 Correct 302 ms 32132 KB Output is correct
16 Correct 264 ms 31204 KB Output is correct
17 Correct 299 ms 33456 KB Output is correct
18 Correct 204 ms 25144 KB Output is correct
19 Correct 172 ms 7920 KB Output is correct
20 Correct 474 ms 32272 KB Output is correct
21 Correct 462 ms 31132 KB Output is correct
22 Correct 434 ms 33340 KB Output is correct
23 Correct 304 ms 25144 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 226 ms 23260 KB Output is correct
4 Correct 223 ms 24484 KB Output is correct
5 Correct 288 ms 23812 KB Output is correct
6 Correct 222 ms 24368 KB Output is correct
7 Correct 228 ms 24120 KB Output is correct
8 Correct 240 ms 23108 KB Output is correct
9 Correct 221 ms 24036 KB Output is correct
10 Correct 268 ms 22868 KB Output is correct

Subtask #3
17.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 0 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 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 572 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 536 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 596 KB Output is correct

Subtask #4
20.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 0 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 137 ms 24956 KB Output is correct
11 Correct 179 ms 30352 KB Output is correct
12 Correct 200 ms 29416 KB Output is correct
13 Correct 236 ms 31372 KB Output is correct
14 Correct 117 ms 23588 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 572 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 2 ms 536 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 14 ms 4112 KB Output is correct
35 Correct 196 ms 31152 KB Output is correct
36 Correct 210 ms 30764 KB Output is correct
37 Correct 216 ms 30020 KB Output is correct
38 Correct 181 ms 28860 KB Output is correct
39 Correct 170 ms 28472 KB Output is correct
40 Correct 151 ms 25852 KB Output is correct
41 Correct 199 ms 31756 KB Output is correct
42 Correct 223 ms 31924 KB Output is correct
43 Correct 113 ms 23612 KB Output is correct
44 Correct 174 ms 28496 KB Output is correct
45 Correct 179 ms 24900 KB Output is correct
46 Correct 196 ms 30776 KB Output is correct
47 Correct 162 ms 27688 KB Output is correct
48 Correct 147 ms 24928 KB Output is correct
49 Correct 115 ms 14372 KB Output is correct
50 Correct 87 ms 10904 KB Output is correct
51 Correct 140 ms 20732 KB Output is correct
52 Correct 262 ms 34372 KB Output is correct
53 Correct 278 ms 32176 KB Output is correct
54 Correct 282 ms 39512 KB Output is correct
55 Correct 125 ms 23604 KB Output is correct
56 Correct 221 ms 30320 KB Output is correct

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 0 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 137 ms 24956 KB Output is correct
10 Correct 179 ms 30352 KB Output is correct
11 Correct 200 ms 29416 KB Output is correct
12 Correct 236 ms 31372 KB Output is correct
13 Correct 117 ms 23588 KB Output is correct
14 Correct 164 ms 24964 KB Output is correct
15 Correct 302 ms 32132 KB Output is correct
16 Correct 264 ms 31204 KB Output is correct
17 Correct 299 ms 33456 KB Output is correct
18 Correct 204 ms 25144 KB Output is correct
19 Correct 226 ms 23260 KB Output is correct
20 Correct 223 ms 24484 KB Output is correct
21 Correct 288 ms 23812 KB Output is correct
22 Correct 222 ms 24368 KB Output is correct
23 Correct 228 ms 24120 KB Output is correct
24 Correct 240 ms 23108 KB Output is correct
25 Correct 221 ms 24036 KB Output is correct
26 Correct 268 ms 22868 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 14 ms 4112 KB Output is correct
37 Correct 196 ms 31152 KB Output is correct
38 Correct 210 ms 30764 KB Output is correct
39 Correct 216 ms 30020 KB Output is correct
40 Correct 181 ms 28860 KB Output is correct
41 Correct 170 ms 28472 KB Output is correct
42 Correct 151 ms 25852 KB Output is correct
43 Correct 199 ms 31756 KB Output is correct
44 Correct 223 ms 31924 KB Output is correct
45 Correct 113 ms 23612 KB Output is correct
46 Correct 174 ms 28496 KB Output is correct
47 Correct 35 ms 3856 KB Output is correct
48 Correct 485 ms 32908 KB Output is correct
49 Correct 441 ms 31800 KB Output is correct
50 Correct 474 ms 31864 KB Output is correct
51 Correct 465 ms 31140 KB Output is correct
52 Correct 443 ms 28600 KB Output is correct
53 Correct 341 ms 20544 KB Output is correct
54 Correct 481 ms 32724 KB Output is correct
55 Correct 451 ms 33668 KB Output is correct
56 Incorrect 276 ms 25156 KB Output isn't correct
57 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 0 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 137 ms 24956 KB Output is correct
11 Correct 179 ms 30352 KB Output is correct
12 Correct 200 ms 29416 KB Output is correct
13 Correct 236 ms 31372 KB Output is correct
14 Correct 117 ms 23588 KB Output is correct
15 Correct 164 ms 24964 KB Output is correct
16 Correct 302 ms 32132 KB Output is correct
17 Correct 264 ms 31204 KB Output is correct
18 Correct 299 ms 33456 KB Output is correct
19 Correct 204 ms 25144 KB Output is correct
20 Correct 226 ms 23260 KB Output is correct
21 Correct 223 ms 24484 KB Output is correct
22 Correct 288 ms 23812 KB Output is correct
23 Correct 222 ms 24368 KB Output is correct
24 Correct 228 ms 24120 KB Output is correct
25 Correct 240 ms 23108 KB Output is correct
26 Correct 221 ms 24036 KB Output is correct
27 Correct 268 ms 22868 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 14 ms 4112 KB Output is correct
38 Correct 196 ms 31152 KB Output is correct
39 Correct 210 ms 30764 KB Output is correct
40 Correct 216 ms 30020 KB Output is correct
41 Correct 181 ms 28860 KB Output is correct
42 Correct 170 ms 28472 KB Output is correct
43 Correct 151 ms 25852 KB Output is correct
44 Correct 199 ms 31756 KB Output is correct
45 Correct 223 ms 31924 KB Output is correct
46 Correct 113 ms 23612 KB Output is correct
47 Correct 174 ms 28496 KB Output is correct
48 Correct 35 ms 3856 KB Output is correct
49 Correct 485 ms 32908 KB Output is correct
50 Correct 441 ms 31800 KB Output is correct
51 Correct 474 ms 31864 KB Output is correct
52 Correct 465 ms 31140 KB Output is correct
53 Correct 443 ms 28600 KB Output is correct
54 Correct 341 ms 20544 KB Output is correct
55 Correct 481 ms 32724 KB Output is correct
56 Correct 451 ms 33668 KB Output is correct
57 Incorrect 276 ms 25156 KB Output isn't correct
58 Halted 0 ms 0 KB -