oj.uz

Submission #712385

# Submission time Handle Problem Language Result Execution time Memory
712385 2023-03-18T17:50:13 Z Ronin13 Swapping Cities (APIO20_swap) C++14
6 / 100
 254 ms 94392 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#include <vector>

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

*/
using namespace std;


const int nmax = 1000000;

vector <vector <pii> > g(nmax);

vector <vector <int> > cmp(nmax);

vector <pii> par[nmax];



int val[nmax];
int l[nmax], r[nmax];
void make_set(int v){
    par[v].pb({v, 0});
    cmp[v].pb(v);
    val[v] = 1e9 + 1;
    l[v] = r[v] = v;
}

void union_sets(int a, int b, int len){
    if(par[a].back().f == par[b].back().f){
        if(val[a] == 1e9 +1){
            int x = par[a].back().f;
            for(int to : cmp[x]){
                val[to] = len;
            }
        }
        return;
    }
    int x = par[a].back().f, y = par[b].back().f;
    if(cmp[x].size() < cmp[y].size())
        swap(x, y), swap(a, b);
    for(int to : cmp[y])
        cmp[x].pb(to), par[to].pb({x, len});
    if(val[x] == 1e9 + 1 || val[y] == 1e9 + 1){
        int mn = min(val[x], val[y]);
        if(mn != 1e9 + 1)
        for(int to : cmp[x])
            val[to] = min(val[to], len);
        return;
    }

    if(l[x] == a && l[y] == b){
        l[x] = r[y];
        return;
    }
    if(l[x] == a && r[y] == b){
        l[x] = l[y];
        return;
    }
    if(r[x] == a && l[y] == b){
        r[x] = r[y];
        return;
    }
    if(r[x] == a && r[y] == b){
        r[x] = l[y];
        return;
    }
    for(int to : cmp[x])
        val[to] =    min(val[to], len);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    int n = N;
    vector <pair <int, pii> > ed;
    for(int i = 0; i < n; i++)
        make_set(i);
    for(int i = 0; i < M; i++){
        ed.pb({W[i], {U[i], V[i]}});
    }
    sort(ed.begin(), ed.end());
    for(int i = 0; i < ed.size(); i++){
        union_sets(ed[i].s.f, ed[i].s.s, ed[i].f);
        //cout << 1;
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if(val[X] == 1e9 + 1)
        return -1;
    int x = X, y = Y;
    int sz = par[x].size() - 1;
    int sz2 = par[y].size() - 1;
    int ans = 1e9 + 1;
    while(sz >= 0 && sz2 >= 0){

        if(par[x][sz].f== par[y][sz2].f)
            ans = min(ans, max(par[x][sz].s, par[y][sz2].s));
        sz--;
        sz2--;
    }
  int u = max(min(val[X],val[y]), ans);
  if(u == 1e9 + 1)
    u = -1;
  return u;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < ed.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 70708 KB Output is correct
2 Correct 35 ms 70712 KB Output is correct
3 Correct 36 ms 70740 KB Output is correct
4 Correct 35 ms 70768 KB Output is correct
5 Correct 35 ms 70916 KB Output is correct
6 Correct 34 ms 70868 KB Output is correct
7 Correct 35 ms 70956 KB Output is correct
8 Correct 35 ms 70900 KB Output is correct
9 Correct 157 ms 87748 KB Output is correct
10 Correct 168 ms 91204 KB Output is correct
11 Correct 189 ms 90932 KB Output is correct
12 Correct 181 ms 92220 KB Output is correct
13 Correct 138 ms 84648 KB Output is correct
14 Correct 140 ms 87804 KB Output is correct
15 Correct 227 ms 93328 KB Output is correct
16 Correct 239 ms 92804 KB Output is correct
17 Correct 254 ms 93960 KB Output is correct
18 Correct 169 ms 86272 KB Output is correct
19 Correct 95 ms 77264 KB Output is correct
20 Correct 243 ms 93528 KB Output is correct
21 Correct 235 ms 93068 KB Output is correct
22 Correct 249 ms 94392 KB Output is correct
23 Correct 183 ms 86712 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 70708 KB Output is correct
2 Correct 35 ms 70712 KB Output is correct
3 Incorrect 162 ms 83532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 70708 KB Output is correct
2 Correct 35 ms 70712 KB Output is correct
3 Correct 36 ms 70740 KB Output is correct
4 Correct 35 ms 70768 KB Output is correct
5 Correct 35 ms 70916 KB Output is correct
6 Correct 34 ms 70868 KB Output is correct
7 Correct 35 ms 70956 KB Output is correct
8 Correct 35 ms 70900 KB Output is correct
9 Correct 33 ms 70740 KB Output is correct
10 Incorrect 33 ms 70908 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70740 KB Output is correct
2 Correct 47 ms 70708 KB Output is correct
3 Correct 35 ms 70712 KB Output is correct
4 Correct 36 ms 70740 KB Output is correct
5 Correct 35 ms 70768 KB Output is correct
6 Correct 35 ms 70916 KB Output is correct
7 Correct 34 ms 70868 KB Output is correct
8 Correct 35 ms 70956 KB Output is correct
9 Correct 35 ms 70900 KB Output is correct
10 Correct 157 ms 87748 KB Output is correct
11 Correct 168 ms 91204 KB Output is correct
12 Correct 189 ms 90932 KB Output is correct
13 Correct 181 ms 92220 KB Output is correct
14 Correct 138 ms 84648 KB Output is correct
15 Incorrect 33 ms 70908 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 70708 KB Output is correct
2 Correct 35 ms 70712 KB Output is correct
3 Correct 36 ms 70740 KB Output is correct
4 Correct 35 ms 70768 KB Output is correct
5 Correct 35 ms 70916 KB Output is correct
6 Correct 34 ms 70868 KB Output is correct
7 Correct 35 ms 70956 KB Output is correct
8 Correct 35 ms 70900 KB Output is correct
9 Correct 157 ms 87748 KB Output is correct
10 Correct 168 ms 91204 KB Output is correct
11 Correct 189 ms 90932 KB Output is correct
12 Correct 181 ms 92220 KB Output is correct
13 Correct 138 ms 84648 KB Output is correct
14 Correct 140 ms 87804 KB Output is correct
15 Correct 227 ms 93328 KB Output is correct
16 Correct 239 ms 92804 KB Output is correct
17 Correct 254 ms 93960 KB Output is correct
18 Correct 169 ms 86272 KB Output is correct
19 Incorrect 162 ms 83532 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70740 KB Output is correct
2 Correct 47 ms 70708 KB Output is correct
3 Correct 35 ms 70712 KB Output is correct
4 Correct 36 ms 70740 KB Output is correct
5 Correct 35 ms 70768 KB Output is correct
6 Correct 35 ms 70916 KB Output is correct
7 Correct 34 ms 70868 KB Output is correct
8 Correct 35 ms 70956 KB Output is correct
9 Correct 35 ms 70900 KB Output is correct
10 Correct 157 ms 87748 KB Output is correct
11 Correct 168 ms 91204 KB Output is correct
12 Correct 189 ms 90932 KB Output is correct
13 Correct 181 ms 92220 KB Output is correct
14 Correct 138 ms 84648 KB Output is correct
15 Correct 140 ms 87804 KB Output is correct
16 Correct 227 ms 93328 KB Output is correct
17 Correct 239 ms 92804 KB Output is correct
18 Correct 254 ms 93960 KB Output is correct
19 Correct 169 ms 86272 KB Output is correct
20 Incorrect 162 ms 83532 KB Output isn't correct
21 Halted 0 ms 0 KB -