oj.uz

Submission #698330

# Submission time Handle Problem Language Result Execution time Memory
698330 2023-02-13T06:48:17 Z whqkrtk04 Swapping Cities (APIO20_swap) C++17
13 / 100
 523 ms 47008 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+50;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

struct UF {
    vector<int> A;
    vector<vector<pii>> P, B, C;
    vector<vector<int>> elements;

    int get(int t, vector<pii> &T) {
        auto iter = upper_bound(T.begin(), T.end(), pii(t, INF));
        return (--iter)->se;
    }

    int fin(int t, int x) {
        return get(t, P[x]);
    }

    int max_deg(int t, int x) {
        return get(t, B[fin(t, x)]);
    }

    int has_cyc(int t, int x) {
        return get(t, C[fin(t, x)]);
    }

    void mer(int t, int x, int y) {
        int xx = P[x].back().se, yy = P[y].back().se;
        if(xx != yy) {
            if(elements[xx].size() < elements[yy].size()) swap(xx, yy), swap(x, y);
            B[xx].push_back({t, max(max(B[xx].back().se, B[yy].back().se), max(++A[x], ++A[y]))});
            B[yy].clear();
            C[xx].push_back({t, C[xx].back().se || C[yy].back().se});
            C[yy].clear();
            for(auto i : elements[yy]) {
                P[i].push_back({t, xx});
                elements[xx].push_back(i);
            }
            elements[yy].clear();
        } else {
            B[xx].push_back({t, max(B[xx].back().se, max(++A[x], ++A[y]))});
            C[xx].push_back({t, 1});
        }
    }

    UF(int n) {
        A.resize(n, 0), B.resize(n, {{0, 0}}), C.resize(n, {{0, 0}});
        elements.resize(n), P.resize(n);
        for(int i = 0; i < n; i++) {
            elements[i].push_back(i);
            P[i].push_back({0, i});
        }
    }
};

int n, m;
vector<piii> E;
UF uf(0);

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    uf = UF(N), n = N, m = M, E.resize(M);
    for(int i = 0; i < M; i++) E[i] = {W[i], {U[i], V[i]}};
    sort(E.begin(), E.end());
    for(auto &i : E) uf.mer(i.fi, i.se.fi, i.se.se);
}

int getMinimumFuelCapacity(int X, int Y) {
    int s = 0, e = INF-5;
    while(s+1 < e) {
        int mi = s+e>>1;
        //cout << s << " " << e << " " << mi << " " << X << " " << Y << " " << mi-1 << "\n";
        if(uf.fin(mi-1, X) == uf.fin(mi-1, Y) && (uf.max_deg(mi-1, X) >= 3 || uf.has_cyc(mi-1, X))) e = mi;
        else s = mi;
    }
    if(s == INF-6) return -1;
    else return s;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mi = s+e>>1;
      |                  ~^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 167 ms 31052 KB Output is correct
10 Correct 217 ms 37692 KB Output is correct
11 Correct 217 ms 36904 KB Output is correct
12 Correct 243 ms 39236 KB Output is correct
13 Correct 134 ms 30672 KB Output is correct
14 Correct 217 ms 31052 KB Output is correct
15 Correct 451 ms 40112 KB Output is correct
16 Correct 469 ms 38840 KB Output is correct
17 Correct 475 ms 41396 KB Output is correct
18 Correct 479 ms 32408 KB Output is correct
19 Correct 259 ms 9680 KB Output is correct
20 Correct 472 ms 45496 KB Output is correct
21 Correct 485 ms 44288 KB Output is correct
22 Correct 523 ms 47008 KB Output is correct
23 Correct 518 ms 38244 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 438 ms 30092 KB Output is correct
4 Correct 422 ms 31352 KB Output is correct
5 Correct 438 ms 30676 KB Output is correct
6 Correct 418 ms 31196 KB Output is correct
7 Correct 436 ms 31060 KB Output is correct
8 Correct 412 ms 29968 KB Output is correct
9 Correct 420 ms 30944 KB Output is correct
10 Correct 434 ms 29684 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 564 KB Output is correct
12 Correct 1 ms 564 KB Output is correct
13 Incorrect 1 ms 468 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 167 ms 31052 KB Output is correct
11 Correct 217 ms 37692 KB Output is correct
12 Correct 217 ms 36904 KB Output is correct
13 Correct 243 ms 39236 KB Output is correct
14 Correct 134 ms 30672 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 564 KB Output is correct
17 Correct 1 ms 564 KB Output is correct
18 Incorrect 1 ms 468 KB Output isn't correct
19 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 167 ms 31052 KB Output is correct
10 Correct 217 ms 37692 KB Output is correct
11 Correct 217 ms 36904 KB Output is correct
12 Correct 243 ms 39236 KB Output is correct
13 Correct 134 ms 30672 KB Output is correct
14 Correct 217 ms 31052 KB Output is correct
15 Correct 451 ms 40112 KB Output is correct
16 Correct 469 ms 38840 KB Output is correct
17 Correct 475 ms 41396 KB Output is correct
18 Correct 479 ms 32408 KB Output is correct
19 Correct 438 ms 30092 KB Output is correct
20 Correct 422 ms 31352 KB Output is correct
21 Correct 438 ms 30676 KB Output is correct
22 Correct 418 ms 31196 KB Output is correct
23 Correct 436 ms 31060 KB Output is correct
24 Correct 412 ms 29968 KB Output is correct
25 Correct 420 ms 30944 KB Output is correct
26 Correct 434 ms 29684 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 564 KB Output is correct
29 Correct 1 ms 564 KB Output is correct
30 Incorrect 1 ms 468 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 167 ms 31052 KB Output is correct
11 Correct 217 ms 37692 KB Output is correct
12 Correct 217 ms 36904 KB Output is correct
13 Correct 243 ms 39236 KB Output is correct
14 Correct 134 ms 30672 KB Output is correct
15 Correct 217 ms 31052 KB Output is correct
16 Correct 451 ms 40112 KB Output is correct
17 Correct 469 ms 38840 KB Output is correct
18 Correct 475 ms 41396 KB Output is correct
19 Correct 479 ms 32408 KB Output is correct
20 Correct 438 ms 30092 KB Output is correct
21 Correct 422 ms 31352 KB Output is correct
22 Correct 438 ms 30676 KB Output is correct
23 Correct 418 ms 31196 KB Output is correct
24 Correct 436 ms 31060 KB Output is correct
25 Correct 412 ms 29968 KB Output is correct
26 Correct 420 ms 30944 KB Output is correct
27 Correct 434 ms 29684 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 564 KB Output is correct
30 Correct 1 ms 564 KB Output is correct
31 Incorrect 1 ms 468 KB Output isn't correct
32 Halted 0 ms 0 KB -