oj.uz

Submission #553128

# Submission time Handle Problem Language Result Execution time Memory
553128 2022-04-24T17:45:44 Z Itamar Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 37780 KB 
#include "swap.h"

#include <cassert>
#include <cstdio>

#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 (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 (it1+1 && it2+1) {
        if (v1[it1].second != v2[it2].second || max(v1[it1].first, v2[it2].first) < s ) {
            return max(v1[it1 + 1].first, v2[it2 + 1].first);
        }
        it1--;
        it2--;
    }

}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:111:26: warning: control reaches end of non-void function [-Wreturn-type]
  111 |     vector<pi> v1 = his[X];
      |                          ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 2 ms 724 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 177 ms 26648 KB Output is correct
10 Correct 213 ms 32184 KB Output is correct
11 Correct 182 ms 31468 KB Output is correct
12 Correct 197 ms 33440 KB Output is correct
13 Correct 150 ms 25656 KB Output is correct
14 Correct 165 ms 26808 KB Output is correct
15 Correct 275 ms 36532 KB Output is correct
16 Correct 313 ms 35420 KB Output is correct
17 Correct 293 ms 37780 KB Output is correct
18 Correct 209 ms 29668 KB Output is correct
19 Incorrect 74 ms 9616 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2052 ms 25232 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 2 ms 724 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 2 ms 724 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 177 ms 26648 KB Output is correct
10 Correct 213 ms 32184 KB Output is correct
11 Correct 182 ms 31468 KB Output is correct
12 Correct 197 ms 33440 KB Output is correct
13 Correct 150 ms 25656 KB Output is correct
14 Correct 165 ms 26808 KB Output is correct
15 Correct 275 ms 36532 KB Output is correct
16 Correct 313 ms 35420 KB Output is correct
17 Correct 293 ms 37780 KB Output is correct
18 Correct 209 ms 29668 KB Output is correct
19 Execution timed out 2052 ms 25232 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -