oj.uz

Submission #553131

# Submission time Handle Problem Language Result Execution time Memory
553131 2022-04-24T18:07:55 Z Itamar Swapping Cities (APIO20_swap) C++14
13 / 100
 307 ms 37812 KB 
#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].second || max(v1[it1].first, v2[it2].first) < s ) {
            return max(max(v1[it1 + 1].first, v2[it2 + 1].first),s);
        }
        
    }

}

Compilation message

swap.cpp:3: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    3 | #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 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 149 ms 24980 KB Output is correct
10 Correct 185 ms 30224 KB Output is correct
11 Correct 189 ms 29432 KB Output is correct
12 Correct 189 ms 31288 KB Output is correct
13 Correct 118 ms 23608 KB Output is correct
14 Correct 158 ms 24976 KB Output is correct
15 Correct 278 ms 32268 KB Output is correct
16 Correct 271 ms 31176 KB Output is correct
17 Correct 307 ms 33336 KB Output is correct
18 Correct 190 ms 25132 KB Output is correct
19 Correct 80 ms 7960 KB Output is correct
20 Correct 294 ms 36608 KB Output is correct
21 Correct 276 ms 35348 KB Output is correct
22 Correct 306 ms 37812 KB Output is correct
23 Correct 204 ms 29464 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 186 ms 23356 KB Output is correct
4 Correct 202 ms 28344 KB Output is correct
5 Correct 190 ms 27632 KB Output is correct
6 Correct 193 ms 28184 KB Output is correct
7 Correct 187 ms 28020 KB Output is correct
8 Correct 185 ms 26936 KB Output is correct
9 Correct 190 ms 27916 KB Output is correct
10 Correct 185 ms 26820 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 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 2 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Incorrect 1 ms 596 KB Output isn't correct
16 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 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 149 ms 24980 KB Output is correct
11 Correct 185 ms 30224 KB Output is correct
12 Correct 189 ms 29432 KB Output is correct
13 Correct 189 ms 31288 KB Output is correct
14 Correct 118 ms 23608 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Incorrect 1 ms 596 KB Output isn't correct
21 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 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 149 ms 24980 KB Output is correct
10 Correct 185 ms 30224 KB Output is correct
11 Correct 189 ms 29432 KB Output is correct
12 Correct 189 ms 31288 KB Output is correct
13 Correct 118 ms 23608 KB Output is correct
14 Correct 158 ms 24976 KB Output is correct
15 Correct 278 ms 32268 KB Output is correct
16 Correct 271 ms 31176 KB Output is correct
17 Correct 307 ms 33336 KB Output is correct
18 Correct 190 ms 25132 KB Output is correct
19 Correct 186 ms 23356 KB Output is correct
20 Correct 202 ms 28344 KB Output is correct
21 Correct 190 ms 27632 KB Output is correct
22 Correct 193 ms 28184 KB Output is correct
23 Correct 187 ms 28020 KB Output is correct
24 Correct 185 ms 26936 KB Output is correct
25 Correct 190 ms 27916 KB Output is correct
26 Correct 185 ms 26820 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Incorrect 1 ms 596 KB Output isn't correct
33 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 149 ms 24980 KB Output is correct
11 Correct 185 ms 30224 KB Output is correct
12 Correct 189 ms 29432 KB Output is correct
13 Correct 189 ms 31288 KB Output is correct
14 Correct 118 ms 23608 KB Output is correct
15 Correct 158 ms 24976 KB Output is correct
16 Correct 278 ms 32268 KB Output is correct
17 Correct 271 ms 31176 KB Output is correct
18 Correct 307 ms 33336 KB Output is correct
19 Correct 190 ms 25132 KB Output is correct
20 Correct 186 ms 23356 KB Output is correct
21 Correct 202 ms 28344 KB Output is correct
22 Correct 190 ms 27632 KB Output is correct
23 Correct 193 ms 28184 KB Output is correct
24 Correct 187 ms 28020 KB Output is correct
25 Correct 185 ms 26936 KB Output is correct
26 Correct 190 ms 27916 KB Output is correct
27 Correct 185 ms 26820 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Incorrect 1 ms 596 KB Output isn't correct
34 Halted 0 ms 0 KB -