oj.uz

Submission #712384

# Submission time Handle Problem Language Result Execution time Memory
712384 2023-03-18T17:48:08 Z Ronin13 Swapping Cities (APIO20_swap) C++14
6 / 100
 254 ms 94476 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] = mn;
        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] = 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:101: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]
  101 |     for(int i = 0; i < ed.size(); i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 33 ms 70732 KB Output is correct
3 Correct 32 ms 70732 KB Output is correct
4 Correct 33 ms 70824 KB Output is correct
5 Correct 36 ms 70896 KB Output is correct
6 Correct 34 ms 70888 KB Output is correct
7 Correct 33 ms 70860 KB Output is correct
8 Correct 33 ms 70908 KB Output is correct
9 Correct 134 ms 87964 KB Output is correct
10 Correct 168 ms 91420 KB Output is correct
11 Correct 166 ms 91116 KB Output is correct
12 Correct 175 ms 92260 KB Output is correct
13 Correct 124 ms 84752 KB Output is correct
14 Correct 142 ms 87924 KB Output is correct
15 Correct 219 ms 93424 KB Output is correct
16 Correct 225 ms 92712 KB Output is correct
17 Correct 245 ms 94168 KB Output is correct
18 Correct 169 ms 86416 KB Output is correct
19 Correct 96 ms 77408 KB Output is correct
20 Correct 240 ms 93636 KB Output is correct
21 Correct 254 ms 93100 KB Output is correct
22 Correct 250 ms 94476 KB Output is correct
23 Correct 208 ms 86808 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 33 ms 70732 KB Output is correct
3 Incorrect 160 ms 83520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 33 ms 70732 KB Output is correct
3 Correct 32 ms 70732 KB Output is correct
4 Correct 33 ms 70824 KB Output is correct
5 Correct 36 ms 70896 KB Output is correct
6 Correct 34 ms 70888 KB Output is correct
7 Correct 33 ms 70860 KB Output is correct
8 Correct 33 ms 70908 KB Output is correct
9 Correct 34 ms 70688 KB Output is correct
10 Incorrect 34 ms 70824 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70688 KB Output is correct
2 Correct 33 ms 70732 KB Output is correct
3 Correct 33 ms 70732 KB Output is correct
4 Correct 32 ms 70732 KB Output is correct
5 Correct 33 ms 70824 KB Output is correct
6 Correct 36 ms 70896 KB Output is correct
7 Correct 34 ms 70888 KB Output is correct
8 Correct 33 ms 70860 KB Output is correct
9 Correct 33 ms 70908 KB Output is correct
10 Correct 134 ms 87964 KB Output is correct
11 Correct 168 ms 91420 KB Output is correct
12 Correct 166 ms 91116 KB Output is correct
13 Correct 175 ms 92260 KB Output is correct
14 Correct 124 ms 84752 KB Output is correct
15 Incorrect 34 ms 70824 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Correct 33 ms 70732 KB Output is correct
3 Correct 32 ms 70732 KB Output is correct
4 Correct 33 ms 70824 KB Output is correct
5 Correct 36 ms 70896 KB Output is correct
6 Correct 34 ms 70888 KB Output is correct
7 Correct 33 ms 70860 KB Output is correct
8 Correct 33 ms 70908 KB Output is correct
9 Correct 134 ms 87964 KB Output is correct
10 Correct 168 ms 91420 KB Output is correct
11 Correct 166 ms 91116 KB Output is correct
12 Correct 175 ms 92260 KB Output is correct
13 Correct 124 ms 84752 KB Output is correct
14 Correct 142 ms 87924 KB Output is correct
15 Correct 219 ms 93424 KB Output is correct
16 Correct 225 ms 92712 KB Output is correct
17 Correct 245 ms 94168 KB Output is correct
18 Correct 169 ms 86416 KB Output is correct
19 Incorrect 160 ms 83520 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70688 KB Output is correct
2 Correct 33 ms 70732 KB Output is correct
3 Correct 33 ms 70732 KB Output is correct
4 Correct 32 ms 70732 KB Output is correct
5 Correct 33 ms 70824 KB Output is correct
6 Correct 36 ms 70896 KB Output is correct
7 Correct 34 ms 70888 KB Output is correct
8 Correct 33 ms 70860 KB Output is correct
9 Correct 33 ms 70908 KB Output is correct
10 Correct 134 ms 87964 KB Output is correct
11 Correct 168 ms 91420 KB Output is correct
12 Correct 166 ms 91116 KB Output is correct
13 Correct 175 ms 92260 KB Output is correct
14 Correct 124 ms 84752 KB Output is correct
15 Correct 142 ms 87924 KB Output is correct
16 Correct 219 ms 93424 KB Output is correct
17 Correct 225 ms 92712 KB Output is correct
18 Correct 245 ms 94168 KB Output is correct
19 Correct 169 ms 86416 KB Output is correct
20 Incorrect 160 ms 83520 KB Output isn't correct
21 Halted 0 ms 0 KB -