oj.uz

Submission #712381

# Submission time Handle Problem Language Result Execution time Memory
712381 2023-03-18T17:43:27 Z Ronin13 Swapping Cities (APIO20_swap) C++14
6 / 100
 2000 ms 98856 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){
        r[x] = r[y];
        return;
    }
    if(r[x] == a && r[y] == b){
        r[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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 32 ms 70732 KB Output is correct
3 Correct 32 ms 70712 KB Output is correct
4 Correct 32 ms 70776 KB Output is correct
5 Correct 34 ms 70884 KB Output is correct
6 Correct 34 ms 70860 KB Output is correct
7 Correct 34 ms 70876 KB Output is correct
8 Correct 33 ms 70844 KB Output is correct
9 Correct 162 ms 89536 KB Output is correct
10 Correct 175 ms 93244 KB Output is correct
11 Correct 175 ms 92928 KB Output is correct
12 Correct 183 ms 94184 KB Output is correct
13 Correct 139 ms 86760 KB Output is correct
14 Correct 193 ms 89708 KB Output is correct
15 Correct 235 ms 97628 KB Output is correct
16 Correct 229 ms 96860 KB Output is correct
17 Correct 303 ms 98496 KB Output is correct
18 Correct 180 ms 90760 KB Output is correct
19 Correct 101 ms 79380 KB Output is correct
20 Correct 329 ms 97684 KB Output is correct
21 Correct 283 ms 97280 KB Output is correct
22 Correct 311 ms 98856 KB Output is correct
23 Correct 228 ms 91100 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 32 ms 70732 KB Output is correct
3 Execution timed out 2069 ms 83264 KB Time limit exceeded
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 32 ms 70732 KB Output is correct
3 Correct 32 ms 70712 KB Output is correct
4 Correct 32 ms 70776 KB Output is correct
5 Correct 34 ms 70884 KB Output is correct
6 Correct 34 ms 70860 KB Output is correct
7 Correct 34 ms 70876 KB Output is correct
8 Correct 33 ms 70844 KB Output is correct
9 Incorrect 34 ms 70732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 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 32 ms 70732 KB Output is correct
3 Correct 32 ms 70712 KB Output is correct
4 Correct 32 ms 70776 KB Output is correct
5 Correct 34 ms 70884 KB Output is correct
6 Correct 34 ms 70860 KB Output is correct
7 Correct 34 ms 70876 KB Output is correct
8 Correct 33 ms 70844 KB Output is correct
9 Correct 162 ms 89536 KB Output is correct
10 Correct 175 ms 93244 KB Output is correct
11 Correct 175 ms 92928 KB Output is correct
12 Correct 183 ms 94184 KB Output is correct
13 Correct 139 ms 86760 KB Output is correct
14 Correct 193 ms 89708 KB Output is correct
15 Correct 235 ms 97628 KB Output is correct
16 Correct 229 ms 96860 KB Output is correct
17 Correct 303 ms 98496 KB Output is correct
18 Correct 180 ms 90760 KB Output is correct
19 Execution timed out 2069 ms 83264 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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