oj.uz

Submission #673933

# Submission time Handle Problem Language Result Execution time Memory
673933 2022-12-22T12:36:36 Z c2zi6 Swapping Cities (APIO20_swap) C++14
0 / 100
 120 ms 12240 KB 
#include "swap.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct EDGE {
    ll u, v, w;
};

struct DSUNODE;
vector<DSUNODE> nodes;
struct DSUNODE {
    ll vert;
    ll parent;
    ll distToParent;
    ll size;
    ll left;
    ll right;
    ll when;
    ll leader(int mxpath = 1e15) {
        if (parent == -1 || distToParent > mxpath) return vert;
        return nodes[nodes[parent].leader(mxpath)].vert;
    }
};

vector<EDGE> edges;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    edges = vector<EDGE>(M);
    nodes = vector<DSUNODE>(N);
    for (int i = 0; i < N; i++) {
        DSUNODE& a = nodes[i];
        a.parent = -1;
        a.distToParent = 0;
        a.size = 1;
        a.vert = a.left = a.right = i;
        a.when = 1e15;
    }
    for (int i = 0; i < M; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.end(), [](const EDGE& a, const EDGE& b){return a.w < b.w;});
    //cout << "WORKS" << endl;
    for (int i = 0; i < M; i++) {
        //cout << nodes[edges[i].u].leader() << " " << nodes[edges[i].v].leader() << endl;
        DSUNODE& u = nodes[nodes[edges[i].u].leader()];
        DSUNODE& v = nodes[nodes[edges[i].v].leader()];
        if (u.vert == v.vert) {
            if ((edges[i].u == u.left && edges[i].v == u.right) || (edges[i].u == u.right && edges[i].v == u.left)) {
                u.left = -1;
                u.right = -1;
                u.when = min(u.when, edges[i].w);
            }
            continue;
        }

        ll newleft = -1, newright = -1;
        if (edges[i].u == u.left && edges[i].v == v.left) {
            newleft = u.right;
            newright = v.right;
        } else if (edges[i].u == u.left && edges[i].v == v.right) {
            newleft = u.right;
            newright = v.left;
        } else if (edges[i].u == u.right && edges[i].v == v.left) {
            newleft = u.left;
            newright = v.right;
        } else if (edges[i].u == u.right && edges[i].v == v.right) {
            newleft = u.left;
            newright = v.left;
        }

        if (u.size > v.size) {
            v.parent = u.vert;
            v.distToParent = edges[i].w;
            u.size += v.size;
            u.left = newleft;
            u.right = newright;
            if (newleft == -1) {
                u.when = min(u.when, edges[i].w);
            }
        } else {
            u.parent = v.vert;
            u.distToParent = edges[i].w;
            v.size += u.size;
            v.left = newleft;
            v.right = newright;
            if (newleft == -1) {
                v.when = min(v.when, edges[i].w);
            }
        }
    }
}

bool can(ll X, ll Y, ll M) {
    ll u = nodes[X].leader(M), v = nodes[Y].leader(M);
    return u == v && M >= nodes[u].when;
}

int getMinimumFuelCapacity(int X, int Y) {
    if (!can(X, Y, 1e15)) return -1;
    ll l = 0, r = 1e15;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (can(X, Y, m)) r = m;
        else l = m;
    }
    return r;
}

int ma2n() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);

  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }

  return 0;
}

Compilation message

swap.cpp:22:28: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   22 |     ll leader(int mxpath = 1e15) {
      |                            ^~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:22:28: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
swap.cpp:22:28: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 35 ms 8276 KB Output is correct
10 Correct 42 ms 10008 KB Output is correct
11 Correct 42 ms 9860 KB Output is correct
12 Correct 45 ms 10440 KB Output is correct
13 Correct 46 ms 10428 KB Output is correct
14 Correct 49 ms 8416 KB Output is correct
15 Correct 98 ms 11864 KB Output is correct
16 Correct 97 ms 11704 KB Output is correct
17 Correct 98 ms 12240 KB Output is correct
18 Correct 120 ms 12224 KB Output is correct
19 Incorrect 46 ms 4116 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 91 ms 11508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 35 ms 8276 KB Output is correct
10 Correct 42 ms 10008 KB Output is correct
11 Correct 42 ms 9860 KB Output is correct
12 Correct 45 ms 10440 KB Output is correct
13 Correct 46 ms 10428 KB Output is correct
14 Correct 49 ms 8416 KB Output is correct
15 Correct 98 ms 11864 KB Output is correct
16 Correct 97 ms 11704 KB Output is correct
17 Correct 98 ms 12240 KB Output is correct
18 Correct 120 ms 12224 KB Output is correct
19 Incorrect 91 ms 11508 KB Output isn't correct
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 -