oj.uz

Submission #553142

# Submission time Handle Problem Language Result Execution time Memory
553142 2022-04-24T18:47:16 Z Itamar Swapping Cities (APIO20_swap) C++14
50 / 100
 480 ms 47704 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);
        }
    }

}

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++) {
      |                     ~~^~~~~~~~~~~~
swap.cpp:125:26: warning: control reaches end of non-void function [-Wreturn-type]
  125 |     vector<pi> v1 = his[X];
      |                          ^

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 2 ms 468 KB Output is correct
9 Correct 162 ms 25012 KB Output is correct
10 Correct 175 ms 30136 KB Output is correct
11 Correct 171 ms 29416 KB Output is correct
12 Correct 233 ms 31360 KB Output is correct
13 Correct 115 ms 23600 KB Output is correct
14 Correct 146 ms 25016 KB Output is correct
15 Correct 306 ms 32244 KB Output is correct
16 Correct 263 ms 31284 KB Output is correct
17 Correct 307 ms 33308 KB Output is correct
18 Correct 201 ms 25120 KB Output is correct
19 Correct 172 ms 7932 KB Output is correct
20 Correct 470 ms 32284 KB Output is correct
21 Correct 447 ms 31060 KB Output is correct
22 Correct 480 ms 33296 KB Output is correct
23 Correct 330 ms 25080 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 229 ms 23424 KB Output is correct
4 Correct 231 ms 24524 KB Output is correct
5 Correct 258 ms 23760 KB Output is correct
6 Correct 227 ms 24376 KB Output is correct
7 Correct 285 ms 24120 KB Output is correct
8 Correct 223 ms 23100 KB Output is correct
9 Correct 297 ms 23956 KB Output is correct
10 Correct 214 ms 22864 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 2 ms 468 KB Output is correct
9 Correct 1 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 436 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 572 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 588 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 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 2 ms 596 KB Output is correct
25 Correct 2 ms 564 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 1 ms 444 KB Output is correct
28 Correct 2 ms 564 KB Output is correct

Subtask #4
20.0 / 20.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 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 2 ms 468 KB Output is correct
10 Correct 162 ms 25012 KB Output is correct
11 Correct 175 ms 30136 KB Output is correct
12 Correct 171 ms 29416 KB Output is correct
13 Correct 233 ms 31360 KB Output is correct
14 Correct 115 ms 23600 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 436 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 1 ms 572 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 564 KB Output is correct
31 Correct 2 ms 596 KB Output is correct
32 Correct 1 ms 444 KB Output is correct
33 Correct 2 ms 564 KB Output is correct
34 Correct 22 ms 4368 KB Output is correct
35 Correct 219 ms 33044 KB Output is correct
36 Correct 187 ms 32476 KB Output is correct
37 Correct 208 ms 31928 KB Output is correct
38 Correct 189 ms 30756 KB Output is correct
39 Correct 172 ms 30272 KB Output is correct
40 Correct 182 ms 27540 KB Output is correct
41 Correct 239 ms 33952 KB Output is correct
42 Correct 217 ms 33696 KB Output is correct
43 Correct 129 ms 25452 KB Output is correct
44 Correct 205 ms 30620 KB Output is correct
45 Correct 169 ms 28080 KB Output is correct
46 Correct 185 ms 32580 KB Output is correct
47 Correct 181 ms 29608 KB Output is correct
48 Correct 137 ms 26920 KB Output is correct
49 Correct 93 ms 17172 KB Output is correct
50 Correct 105 ms 13264 KB Output is correct
51 Correct 144 ms 23540 KB Output is correct
52 Correct 307 ms 37776 KB Output is correct
53 Correct 239 ms 36008 KB Output is correct
54 Correct 280 ms 43440 KB Output is correct
55 Correct 133 ms 25360 KB Output is correct
56 Correct 209 ms 34012 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 2 ms 468 KB Output is correct
9 Correct 162 ms 25012 KB Output is correct
10 Correct 175 ms 30136 KB Output is correct
11 Correct 171 ms 29416 KB Output is correct
12 Correct 233 ms 31360 KB Output is correct
13 Correct 115 ms 23600 KB Output is correct
14 Correct 146 ms 25016 KB Output is correct
15 Correct 306 ms 32244 KB Output is correct
16 Correct 263 ms 31284 KB Output is correct
17 Correct 307 ms 33308 KB Output is correct
18 Correct 201 ms 25120 KB Output is correct
19 Correct 229 ms 23424 KB Output is correct
20 Correct 231 ms 24524 KB Output is correct
21 Correct 258 ms 23760 KB Output is correct
22 Correct 227 ms 24376 KB Output is correct
23 Correct 285 ms 24120 KB Output is correct
24 Correct 223 ms 23100 KB Output is correct
25 Correct 297 ms 23956 KB Output is correct
26 Correct 214 ms 22864 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 436 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 1 ms 572 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 2 ms 588 KB Output is correct
36 Correct 22 ms 4368 KB Output is correct
37 Correct 219 ms 33044 KB Output is correct
38 Correct 187 ms 32476 KB Output is correct
39 Correct 208 ms 31928 KB Output is correct
40 Correct 189 ms 30756 KB Output is correct
41 Correct 172 ms 30272 KB Output is correct
42 Correct 182 ms 27540 KB Output is correct
43 Correct 239 ms 33952 KB Output is correct
44 Correct 217 ms 33696 KB Output is correct
45 Correct 129 ms 25452 KB Output is correct
46 Correct 205 ms 30620 KB Output is correct
47 Correct 36 ms 4332 KB Output is correct
48 Correct 468 ms 36960 KB Output is correct
49 Correct 448 ms 35968 KB Output is correct
50 Correct 441 ms 36004 KB Output is correct
51 Correct 454 ms 35080 KB Output is correct
52 Correct 430 ms 32720 KB Output is correct
53 Correct 299 ms 24248 KB Output is correct
54 Correct 464 ms 37176 KB Output is correct
55 Correct 479 ms 37832 KB Output is correct
56 Runtime error 195 ms 47704 KB Execution killed with signal 6
57 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 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 2 ms 468 KB Output is correct
10 Correct 162 ms 25012 KB Output is correct
11 Correct 175 ms 30136 KB Output is correct
12 Correct 171 ms 29416 KB Output is correct
13 Correct 233 ms 31360 KB Output is correct
14 Correct 115 ms 23600 KB Output is correct
15 Correct 146 ms 25016 KB Output is correct
16 Correct 306 ms 32244 KB Output is correct
17 Correct 263 ms 31284 KB Output is correct
18 Correct 307 ms 33308 KB Output is correct
19 Correct 201 ms 25120 KB Output is correct
20 Correct 229 ms 23424 KB Output is correct
21 Correct 231 ms 24524 KB Output is correct
22 Correct 258 ms 23760 KB Output is correct
23 Correct 227 ms 24376 KB Output is correct
24 Correct 285 ms 24120 KB Output is correct
25 Correct 223 ms 23100 KB Output is correct
26 Correct 297 ms 23956 KB Output is correct
27 Correct 214 ms 22864 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 436 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 2 ms 468 KB Output is correct
34 Correct 1 ms 572 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 2 ms 588 KB Output is correct
37 Correct 22 ms 4368 KB Output is correct
38 Correct 219 ms 33044 KB Output is correct
39 Correct 187 ms 32476 KB Output is correct
40 Correct 208 ms 31928 KB Output is correct
41 Correct 189 ms 30756 KB Output is correct
42 Correct 172 ms 30272 KB Output is correct
43 Correct 182 ms 27540 KB Output is correct
44 Correct 239 ms 33952 KB Output is correct
45 Correct 217 ms 33696 KB Output is correct
46 Correct 129 ms 25452 KB Output is correct
47 Correct 205 ms 30620 KB Output is correct
48 Correct 36 ms 4332 KB Output is correct
49 Correct 468 ms 36960 KB Output is correct
50 Correct 448 ms 35968 KB Output is correct
51 Correct 441 ms 36004 KB Output is correct
52 Correct 454 ms 35080 KB Output is correct
53 Correct 430 ms 32720 KB Output is correct
54 Correct 299 ms 24248 KB Output is correct
55 Correct 464 ms 37176 KB Output is correct
56 Correct 479 ms 37832 KB Output is correct
57 Runtime error 195 ms 47704 KB Execution killed with signal 6
58 Halted 0 ms 0 KB -