oj.uz

Submission #1059812

# Submission time Handle Problem Language Result Execution time Memory
1059812 2024-08-15T08:25:25 Z mispertion Swapping Cities (APIO20_swap) C++17
7 / 100
 466 ms 43968 KB 
#include "swap.h"
#include <bits/stdc++.h>
#include <vector>

#pragma gcc optimize("unroll-loops")
#pragma gcc optimize("o3")
#pragma gcc optimize("Ofast")

using namespace std;

const int N = 1e5 + 5;
const int infi = INT_MAX;

typedef pair<int, int> pii;

#define mp make_pair
#define pb push_back
#define F first
#define S second

struct dsu{
    int pw[N];
    vector<pii> p[N], cnt1[N], cnt2[N], sz[N];

    dsu(int n){
        for(int i = 1; i <= n; i++){
            p[i] = {{-1, i}};
            sz[i] = {{-1, 1}};
            cnt1[i] = {{-1, 0}};
            cnt2[i] = {{-1, 0}};
            pw[i] = 0;
        }
    }
    dsu(){

    }

    int getp(int v, int t){
        int pos = (--upper_bound(p[v].begin(), p[v].end(),mp(t, infi))) - p[v].begin();
        int pr = p[v][pos].S;
        if(pr == v)
            return v;
        return p[v][pos].S = getp(pr, t);
    }

    void upd(int v, int nw, int t){
        if(nw == 1)
            cnt1[v].pb({t, cnt1[v].back().S - 1});
        if(nw == 2)
            cnt2[v].pb({t, cnt2[v].back().S - 1});
        if(nw == 0)
            cnt1[v].pb({t, cnt1[v].back().S + 1});
        if(nw == 1)
            cnt2[v].pb({t, cnt2[v].back().S + 1});
    }

    void uni(int a, int b, int t){
        int n1 = pw[a];
        int n2 = pw[b];
        //cout << n1 << ' ' << n2 << '\n';
        pw[a]++;
        pw[b]++;
        a = getp(a, t);
        b = getp(b, t);
        if(a == b){
            upd(a, n1, t);
            upd(a, n2, t);
            return;
        }
        if(sz[a] > sz[b])
            swap(a, b);
        p[a].pb({t, b});
        sz[b].pb({t, sz[a].back().S + sz[b].back().S});
        cnt1[b].pb({t, cnt1[a].back().S + cnt1[b].back().S});
        cnt2[b].pb({t, cnt2[a].back().S + cnt2[b].back().S});
        upd(b, n1, t);
        upd(b, n2, t);
    }
};

int n, m;
vector<pair<int, pair<int, int>>> edges;
dsu ds;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;
    for(int i = 0; i < m; i++){
        U[i]++;
        V[i]++;
        edges.pb({W[i], {V[i], U[i]}});
    }
    sort(edges.begin(), edges.end());
    ds = dsu(n);
    for(int i = 0; i < m; i++){
        ds.uni(edges[i].S.F, edges[i].S.S, i);
        /*cout << "comp: ";
        for(int j = 1; j <= n; j++){
            cout << ds.getp(j, infi) << ' ';
        }
        cout << '\n';
        cout << "cnt1: ";
        for(int i = 1; i <= n; i++){
            cout << ds.cnt1[ds.getp(i, infi)].back().S << ' ';
        }
        cout << '\n';
        cout << "cnt2: ";
        for(int i = 1; i <= n; i++){
            cout << ds.cnt2[ds.getp(i, infi)].back().S << ' ';
        }
        cout << '\n';*/
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;
    int lo = -1, hi = m;
    while(lo + 1 < hi){
        int m = (lo + hi) / 2;
        int x = ds.getp(X, m), y = ds.getp(Y, m);
        if(x != y){
            lo = m;
            continue;
        }
        int c1 = (--upper_bound(ds.cnt1[x].begin(), ds.cnt1[x].end(),mp(m, infi)))->S;
        int c2 = (--upper_bound(ds.cnt2[x].begin(), ds.cnt2[x].end(),mp(m, infi)))->S;
        int sz = (--upper_bound(ds.sz[x].begin(), ds.sz[x].end(),mp(m, infi)))->S;
        if(c1 == 2 && c2 == sz - 2){
            lo = m;
            continue;
        }
        hi = m;
    }
    if(hi == m)
        return -1;
    return edges[hi].F;
}

Compilation message

swap.cpp:5: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    5 | #pragma gcc optimize("unroll-loops")
      | 
swap.cpp:6: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    6 | #pragma gcc optimize("o3")
      | 
swap.cpp:7: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      |

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19800 KB Output is correct
2 Correct 13 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 8 ms 20060 KB Output is correct
5 Correct 9 ms 20060 KB Output is correct
6 Correct 10 ms 20140 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 8 ms 20060 KB Output is correct
9 Correct 85 ms 38884 KB Output is correct
10 Correct 91 ms 42952 KB Output is correct
11 Correct 126 ms 42488 KB Output is correct
12 Correct 131 ms 43968 KB Output is correct
13 Correct 68 ms 43208 KB Output is correct
14 Incorrect 96 ms 38856 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19800 KB Output is correct
2 Correct 13 ms 19804 KB Output is correct
3 Correct 444 ms 41644 KB Output is correct
4 Correct 431 ms 42500 KB Output is correct
5 Correct 466 ms 41952 KB Output is correct
6 Correct 405 ms 42300 KB Output is correct
7 Correct 430 ms 42308 KB Output is correct
8 Correct 417 ms 41584 KB Output is correct
9 Correct 441 ms 42164 KB Output is correct
10 Correct 430 ms 41336 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19800 KB Output is correct
2 Correct 13 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 8 ms 20060 KB Output is correct
5 Correct 9 ms 20060 KB Output is correct
6 Correct 10 ms 20140 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 8 ms 20060 KB Output is correct
9 Correct 8 ms 19800 KB Output is correct
10 Incorrect 8 ms 20056 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19800 KB Output is correct
2 Correct 12 ms 19800 KB Output is correct
3 Correct 13 ms 19804 KB Output is correct
4 Correct 8 ms 19804 KB Output is correct
5 Correct 8 ms 20060 KB Output is correct
6 Correct 9 ms 20060 KB Output is correct
7 Correct 10 ms 20140 KB Output is correct
8 Correct 10 ms 20060 KB Output is correct
9 Correct 8 ms 20060 KB Output is correct
10 Correct 85 ms 38884 KB Output is correct
11 Correct 91 ms 42952 KB Output is correct
12 Correct 126 ms 42488 KB Output is correct
13 Correct 131 ms 43968 KB Output is correct
14 Correct 68 ms 43208 KB Output is correct
15 Incorrect 8 ms 20056 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19800 KB Output is correct
2 Correct 13 ms 19804 KB Output is correct
3 Correct 8 ms 19804 KB Output is correct
4 Correct 8 ms 20060 KB Output is correct
5 Correct 9 ms 20060 KB Output is correct
6 Correct 10 ms 20140 KB Output is correct
7 Correct 10 ms 20060 KB Output is correct
8 Correct 8 ms 20060 KB Output is correct
9 Correct 85 ms 38884 KB Output is correct
10 Correct 91 ms 42952 KB Output is correct
11 Correct 126 ms 42488 KB Output is correct
12 Correct 131 ms 43968 KB Output is correct
13 Correct 68 ms 43208 KB Output is correct
14 Incorrect 96 ms 38856 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19800 KB Output is correct
2 Correct 12 ms 19800 KB Output is correct
3 Correct 13 ms 19804 KB Output is correct
4 Correct 8 ms 19804 KB Output is correct
5 Correct 8 ms 20060 KB Output is correct
6 Correct 9 ms 20060 KB Output is correct
7 Correct 10 ms 20140 KB Output is correct
8 Correct 10 ms 20060 KB Output is correct
9 Correct 8 ms 20060 KB Output is correct
10 Correct 85 ms 38884 KB Output is correct
11 Correct 91 ms 42952 KB Output is correct
12 Correct 126 ms 42488 KB Output is correct
13 Correct 131 ms 43968 KB Output is correct
14 Correct 68 ms 43208 KB Output is correct
15 Incorrect 96 ms 38856 KB Output isn't correct
16 Halted 0 ms 0 KB -