oj.uz

Submission #553138

# Submission time Handle Problem Language Result Execution time Memory
553138 2022-04-24T18:22:30 Z Itamar Swapping Cities (APIO20_swap) C++14
13 / 100
 321 ms 33356 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(v1[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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 170 ms 25012 KB Output is correct
10 Correct 202 ms 30196 KB Output is correct
11 Correct 203 ms 29444 KB Output is correct
12 Correct 222 ms 31316 KB Output is correct
13 Correct 142 ms 23584 KB Output is correct
14 Correct 173 ms 24948 KB Output is correct
15 Correct 314 ms 32156 KB Output is correct
16 Correct 287 ms 31160 KB Output is correct
17 Correct 296 ms 33324 KB Output is correct
18 Correct 194 ms 25168 KB Output is correct
19 Correct 89 ms 7880 KB Output is correct
20 Correct 312 ms 32312 KB Output is correct
21 Correct 296 ms 31052 KB Output is correct
22 Correct 321 ms 33356 KB Output is correct
23 Correct 213 ms 25132 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 194 ms 23320 KB Output is correct
4 Correct 196 ms 24520 KB Output is correct
5 Correct 206 ms 23664 KB Output is correct
6 Correct 189 ms 24380 KB Output is correct
7 Correct 187 ms 24200 KB Output is correct
8 Correct 216 ms 23116 KB Output is correct
9 Correct 181 ms 24020 KB Output is correct
10 Correct 209 ms 22868 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 Incorrect 1 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 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 170 ms 25012 KB Output is correct
11 Correct 202 ms 30196 KB Output is correct
12 Correct 203 ms 29444 KB Output is correct
13 Correct 222 ms 31316 KB Output is correct
14 Correct 142 ms 23584 KB Output is correct
15 Incorrect 1 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 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 170 ms 25012 KB Output is correct
10 Correct 202 ms 30196 KB Output is correct
11 Correct 203 ms 29444 KB Output is correct
12 Correct 222 ms 31316 KB Output is correct
13 Correct 142 ms 23584 KB Output is correct
14 Correct 173 ms 24948 KB Output is correct
15 Correct 314 ms 32156 KB Output is correct
16 Correct 287 ms 31160 KB Output is correct
17 Correct 296 ms 33324 KB Output is correct
18 Correct 194 ms 25168 KB Output is correct
19 Correct 194 ms 23320 KB Output is correct
20 Correct 196 ms 24520 KB Output is correct
21 Correct 206 ms 23664 KB Output is correct
22 Correct 189 ms 24380 KB Output is correct
23 Correct 187 ms 24200 KB Output is correct
24 Correct 216 ms 23116 KB Output is correct
25 Correct 181 ms 24020 KB Output is correct
26 Correct 209 ms 22868 KB Output is correct
27 Incorrect 1 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 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 170 ms 25012 KB Output is correct
11 Correct 202 ms 30196 KB Output is correct
12 Correct 203 ms 29444 KB Output is correct
13 Correct 222 ms 31316 KB Output is correct
14 Correct 142 ms 23584 KB Output is correct
15 Correct 173 ms 24948 KB Output is correct
16 Correct 314 ms 32156 KB Output is correct
17 Correct 287 ms 31160 KB Output is correct
18 Correct 296 ms 33324 KB Output is correct
19 Correct 194 ms 25168 KB Output is correct
20 Correct 194 ms 23320 KB Output is correct
21 Correct 196 ms 24520 KB Output is correct
22 Correct 206 ms 23664 KB Output is correct
23 Correct 189 ms 24380 KB Output is correct
24 Correct 187 ms 24200 KB Output is correct
25 Correct 216 ms 23116 KB Output is correct
26 Correct 181 ms 24020 KB Output is correct
27 Correct 209 ms 22868 KB Output is correct
28 Incorrect 1 ms 468 KB Output isn't correct
29 Halted 0 ms 0 KB -