oj.uz

Submission #712378

# Submission time Handle Problem Language Result Execution time Memory
712378 2023-03-18T17:39:29 Z Ronin13 Swapping Cities (APIO20_swap) C++14
0 / 100
 151 ms 87324 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]);

        for(int to : cmp[x])
            val[to] = mn;
    }
    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){
        l[x] = r[y];
        return;
    }
    if(r[x] == a && r[y] == b){
        l[x] = l[y];
        return;
    }
    for(int to : cmp[x])
        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:100: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]
  100 |     for(int i = 0; i < ed.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70752 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Incorrect 33 ms 70740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70752 KB Output is correct
3 Incorrect 151 ms 87324 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70752 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Incorrect 33 ms 70740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70752 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Incorrect 33 ms 70740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70752 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Incorrect 33 ms 70740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70752 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Incorrect 33 ms 70740 KB Output isn't correct
5 Halted 0 ms 0 KB -