oj.uz

Submission #553137

# Submission time Handle Problem Language Result Execution time Memory
553137 2022-04-24T18:21:26 Z Itamar Swapping Cities (APIO20_swap) C++14
13 / 100
 313 ms 33444 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(v2[it2+1].first, s);
        }
        if (v1[it1+1].second != v2[it2 ].second) {
            return max(v2[it1 + 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 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 556 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 141 ms 25072 KB Output is correct
10 Correct 187 ms 30084 KB Output is correct
11 Correct 209 ms 29416 KB Output is correct
12 Correct 195 ms 31412 KB Output is correct
13 Correct 115 ms 23500 KB Output is correct
14 Correct 160 ms 24996 KB Output is correct
15 Correct 293 ms 32144 KB Output is correct
16 Correct 264 ms 31216 KB Output is correct
17 Correct 313 ms 33444 KB Output is correct
18 Correct 223 ms 25116 KB Output is correct
19 Correct 73 ms 7956 KB Output is correct
20 Correct 275 ms 32312 KB Output is correct
21 Correct 283 ms 31112 KB Output is correct
22 Correct 289 ms 33208 KB Output is correct
23 Correct 228 ms 25156 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 184 ms 23344 KB Output is correct
4 Correct 216 ms 24524 KB Output is correct
5 Correct 185 ms 23708 KB Output is correct
6 Correct 210 ms 24368 KB Output is correct
7 Correct 183 ms 24060 KB Output is correct
8 Correct 190 ms 23256 KB Output is correct
9 Correct 245 ms 24036 KB Output is correct
10 Correct 174 ms 22876 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 556 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 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 556 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 141 ms 25072 KB Output is correct
11 Correct 187 ms 30084 KB Output is correct
12 Correct 209 ms 29416 KB Output is correct
13 Correct 195 ms 31412 KB Output is correct
14 Correct 115 ms 23500 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 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 556 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 141 ms 25072 KB Output is correct
10 Correct 187 ms 30084 KB Output is correct
11 Correct 209 ms 29416 KB Output is correct
12 Correct 195 ms 31412 KB Output is correct
13 Correct 115 ms 23500 KB Output is correct
14 Correct 160 ms 24996 KB Output is correct
15 Correct 293 ms 32144 KB Output is correct
16 Correct 264 ms 31216 KB Output is correct
17 Correct 313 ms 33444 KB Output is correct
18 Correct 223 ms 25116 KB Output is correct
19 Correct 184 ms 23344 KB Output is correct
20 Correct 216 ms 24524 KB Output is correct
21 Correct 185 ms 23708 KB Output is correct
22 Correct 210 ms 24368 KB Output is correct
23 Correct 183 ms 24060 KB Output is correct
24 Correct 190 ms 23256 KB Output is correct
25 Correct 245 ms 24036 KB Output is correct
26 Correct 174 ms 22876 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 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 556 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 141 ms 25072 KB Output is correct
11 Correct 187 ms 30084 KB Output is correct
12 Correct 209 ms 29416 KB Output is correct
13 Correct 195 ms 31412 KB Output is correct
14 Correct 115 ms 23500 KB Output is correct
15 Correct 160 ms 24996 KB Output is correct
16 Correct 293 ms 32144 KB Output is correct
17 Correct 264 ms 31216 KB Output is correct
18 Correct 313 ms 33444 KB Output is correct
19 Correct 223 ms 25116 KB Output is correct
20 Correct 184 ms 23344 KB Output is correct
21 Correct 216 ms 24524 KB Output is correct
22 Correct 185 ms 23708 KB Output is correct
23 Correct 210 ms 24368 KB Output is correct
24 Correct 183 ms 24060 KB Output is correct
25 Correct 190 ms 23256 KB Output is correct
26 Correct 245 ms 24036 KB Output is correct
27 Correct 174 ms 22876 KB Output is correct
28 Incorrect 2 ms 468 KB Output isn't correct
29 Halted 0 ms 0 KB -