oj.uz

Submission #698328

# Submission time Handle Problem Language Result Execution time Memory
698328 2023-02-13T06:43:15 Z whqkrtk04 Swapping Cities (APIO20_swap) C++17
7 / 100
 560 ms 36164 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) {
        int p = get(t, P[x]);
        if(p == x) return x;
        else return fin(t, p);
    }

    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);
            P[yy].push_back({t, xx});
            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]) 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 572 KB Output is correct
9 Correct 118 ms 25292 KB Output is correct
10 Correct 146 ms 30796 KB Output is correct
11 Correct 143 ms 30320 KB Output is correct
12 Correct 168 ms 32064 KB Output is correct
13 Correct 105 ms 30852 KB Output is correct
14 Correct 143 ms 25532 KB Output is correct
15 Correct 384 ms 35104 KB Output is correct
16 Correct 385 ms 34296 KB Output is correct
17 Correct 409 ms 36164 KB Output is correct
18 Correct 560 ms 34972 KB Output is correct
19 Incorrect 190 ms 9292 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 476 ms 33880 KB Output is correct
4 Correct 498 ms 35276 KB Output is correct
5 Correct 545 ms 34636 KB Output is correct
6 Correct 491 ms 35044 KB Output is correct
7 Correct 516 ms 35008 KB Output is correct
8 Correct 478 ms 33896 KB Output is correct
9 Correct 486 ms 34632 KB Output is correct
10 Correct 539 ms 33536 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 0 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 572 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Incorrect 1 ms 584 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 584 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 572 KB Output is correct
10 Correct 118 ms 25292 KB Output is correct
11 Correct 146 ms 30796 KB Output is correct
12 Correct 143 ms 30320 KB Output is correct
13 Correct 168 ms 32064 KB Output is correct
14 Correct 105 ms 30852 KB Output is correct
15 Incorrect 1 ms 584 KB Output isn't correct
16 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 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 572 KB Output is correct
9 Correct 118 ms 25292 KB Output is correct
10 Correct 146 ms 30796 KB Output is correct
11 Correct 143 ms 30320 KB Output is correct
12 Correct 168 ms 32064 KB Output is correct
13 Correct 105 ms 30852 KB Output is correct
14 Correct 143 ms 25532 KB Output is correct
15 Correct 384 ms 35104 KB Output is correct
16 Correct 385 ms 34296 KB Output is correct
17 Correct 409 ms 36164 KB Output is correct
18 Correct 560 ms 34972 KB Output is correct
19 Correct 476 ms 33880 KB Output is correct
20 Correct 498 ms 35276 KB Output is correct
21 Correct 545 ms 34636 KB Output is correct
22 Correct 491 ms 35044 KB Output is correct
23 Correct 516 ms 35008 KB Output is correct
24 Correct 478 ms 33896 KB Output is correct
25 Correct 486 ms 34632 KB Output is correct
26 Correct 539 ms 33536 KB Output is correct
27 Incorrect 1 ms 584 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 584 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 572 KB Output is correct
10 Correct 118 ms 25292 KB Output is correct
11 Correct 146 ms 30796 KB Output is correct
12 Correct 143 ms 30320 KB Output is correct
13 Correct 168 ms 32064 KB Output is correct
14 Correct 105 ms 30852 KB Output is correct
15 Correct 143 ms 25532 KB Output is correct
16 Correct 384 ms 35104 KB Output is correct
17 Correct 385 ms 34296 KB Output is correct
18 Correct 409 ms 36164 KB Output is correct
19 Correct 560 ms 34972 KB Output is correct
20 Correct 476 ms 33880 KB Output is correct
21 Correct 498 ms 35276 KB Output is correct
22 Correct 545 ms 34636 KB Output is correct
23 Correct 491 ms 35044 KB Output is correct
24 Correct 516 ms 35008 KB Output is correct
25 Correct 478 ms 33896 KB Output is correct
26 Correct 486 ms 34632 KB Output is correct
27 Correct 539 ms 33536 KB Output is correct
28 Incorrect 1 ms 584 KB Output isn't correct
29 Halted 0 ms 0 KB -