oj.uz

Submission #698326

# Submission time Handle Problem Language Result Execution time Memory
698326 2023-02-13T06:42:05 Z whqkrtk04 Swapping Cities (APIO20_swap) C++17
7 / 100
 576 ms 36140 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+1;
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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 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 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 128 ms 25184 KB Output is correct
10 Correct 164 ms 30884 KB Output is correct
11 Correct 157 ms 30312 KB Output is correct
12 Correct 159 ms 32076 KB Output is correct
13 Correct 99 ms 30732 KB Output is correct
14 Correct 164 ms 25500 KB Output is correct
15 Correct 395 ms 35232 KB Output is correct
16 Correct 426 ms 34264 KB Output is correct
17 Correct 447 ms 36140 KB Output is correct
18 Correct 576 ms 34988 KB Output is correct
19 Incorrect 178 ms 9228 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 512 ms 33988 KB Output is correct
4 Correct 473 ms 35160 KB Output is correct
5 Correct 531 ms 34708 KB Output is correct
6 Correct 477 ms 35156 KB Output is correct
7 Correct 511 ms 35020 KB Output is correct
8 Correct 474 ms 33800 KB Output is correct
9 Correct 503 ms 34648 KB Output is correct
10 Correct 508 ms 33544 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 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 468 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 Incorrect 1 ms 580 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 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 468 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 128 ms 25184 KB Output is correct
11 Correct 164 ms 30884 KB Output is correct
12 Correct 157 ms 30312 KB Output is correct
13 Correct 159 ms 32076 KB Output is correct
14 Correct 99 ms 30732 KB Output is correct
15 Incorrect 1 ms 580 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 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 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 128 ms 25184 KB Output is correct
10 Correct 164 ms 30884 KB Output is correct
11 Correct 157 ms 30312 KB Output is correct
12 Correct 159 ms 32076 KB Output is correct
13 Correct 99 ms 30732 KB Output is correct
14 Correct 164 ms 25500 KB Output is correct
15 Correct 395 ms 35232 KB Output is correct
16 Correct 426 ms 34264 KB Output is correct
17 Correct 447 ms 36140 KB Output is correct
18 Correct 576 ms 34988 KB Output is correct
19 Correct 512 ms 33988 KB Output is correct
20 Correct 473 ms 35160 KB Output is correct
21 Correct 531 ms 34708 KB Output is correct
22 Correct 477 ms 35156 KB Output is correct
23 Correct 511 ms 35020 KB Output is correct
24 Correct 474 ms 33800 KB Output is correct
25 Correct 503 ms 34648 KB Output is correct
26 Correct 508 ms 33544 KB Output is correct
27 Incorrect 1 ms 580 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 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 468 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 128 ms 25184 KB Output is correct
11 Correct 164 ms 30884 KB Output is correct
12 Correct 157 ms 30312 KB Output is correct
13 Correct 159 ms 32076 KB Output is correct
14 Correct 99 ms 30732 KB Output is correct
15 Correct 164 ms 25500 KB Output is correct
16 Correct 395 ms 35232 KB Output is correct
17 Correct 426 ms 34264 KB Output is correct
18 Correct 447 ms 36140 KB Output is correct
19 Correct 576 ms 34988 KB Output is correct
20 Correct 512 ms 33988 KB Output is correct
21 Correct 473 ms 35160 KB Output is correct
22 Correct 531 ms 34708 KB Output is correct
23 Correct 477 ms 35156 KB Output is correct
24 Correct 511 ms 35020 KB Output is correct
25 Correct 474 ms 33800 KB Output is correct
26 Correct 503 ms 34648 KB Output is correct
27 Correct 508 ms 33544 KB Output is correct
28 Incorrect 1 ms 580 KB Output isn't correct
29 Halted 0 ms 0 KB -