oj.uz

Submission #1059986

# Submission time Handle Problem Language Result Execution time Memory
1059986 2024-08-15T09:53:18 Z mispertion Swapping Cities (APIO20_swap) C++17
0 / 100
 193 ms 54864 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 sz(x) (int)x.size()
#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];
    vector<int> st[N];

    dsu(int n){
        for(int i = 1; i <= n; i++){
            st[i] = {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();
        return p[v][pos].S;
    }

    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(st[a]) > sz(st[b]))
            swap(a, b);
        if(sz(st[b]) > 21){
            return;
        }
        sz[b].pb({t, sz[b].back().S + sz[a].back().S});
        for(auto e : st[a]){
            st[b].pb(e);
            p[e].pb({t, b});
        }
        st[a].clear();
        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 11 ms 24668 KB Output is correct
2 Correct 11 ms 24696 KB Output is correct
3 Correct 11 ms 24544 KB Output is correct
4 Correct 10 ms 24668 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 10 ms 24832 KB Output is correct
7 Correct 11 ms 24920 KB Output is correct
8 Correct 10 ms 24924 KB Output is correct
9 Correct 97 ms 47560 KB Output is correct
10 Correct 126 ms 52564 KB Output is correct
11 Correct 117 ms 52160 KB Output is correct
12 Correct 119 ms 53704 KB Output is correct
13 Correct 88 ms 50372 KB Output is correct
14 Correct 103 ms 47556 KB Output is correct
15 Incorrect 193 ms 54864 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24696 KB Output is correct
3 Incorrect 125 ms 44908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24696 KB Output is correct
3 Correct 11 ms 24544 KB Output is correct
4 Correct 10 ms 24668 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 10 ms 24832 KB Output is correct
7 Correct 11 ms 24920 KB Output is correct
8 Correct 10 ms 24924 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Incorrect 11 ms 24888 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24668 KB Output is correct
2 Correct 11 ms 24668 KB Output is correct
3 Correct 11 ms 24696 KB Output is correct
4 Correct 11 ms 24544 KB Output is correct
5 Correct 10 ms 24668 KB Output is correct
6 Correct 11 ms 24924 KB Output is correct
7 Correct 10 ms 24832 KB Output is correct
8 Correct 11 ms 24920 KB Output is correct
9 Correct 10 ms 24924 KB Output is correct
10 Correct 97 ms 47560 KB Output is correct
11 Correct 126 ms 52564 KB Output is correct
12 Correct 117 ms 52160 KB Output is correct
13 Correct 119 ms 53704 KB Output is correct
14 Correct 88 ms 50372 KB Output is correct
15 Incorrect 11 ms 24888 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24696 KB Output is correct
3 Correct 11 ms 24544 KB Output is correct
4 Correct 10 ms 24668 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 10 ms 24832 KB Output is correct
7 Correct 11 ms 24920 KB Output is correct
8 Correct 10 ms 24924 KB Output is correct
9 Correct 97 ms 47560 KB Output is correct
10 Correct 126 ms 52564 KB Output is correct
11 Correct 117 ms 52160 KB Output is correct
12 Correct 119 ms 53704 KB Output is correct
13 Correct 88 ms 50372 KB Output is correct
14 Correct 103 ms 47556 KB Output is correct
15 Incorrect 193 ms 54864 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24668 KB Output is correct
2 Correct 11 ms 24668 KB Output is correct
3 Correct 11 ms 24696 KB Output is correct
4 Correct 11 ms 24544 KB Output is correct
5 Correct 10 ms 24668 KB Output is correct
6 Correct 11 ms 24924 KB Output is correct
7 Correct 10 ms 24832 KB Output is correct
8 Correct 11 ms 24920 KB Output is correct
9 Correct 10 ms 24924 KB Output is correct
10 Correct 97 ms 47560 KB Output is correct
11 Correct 126 ms 52564 KB Output is correct
12 Correct 117 ms 52160 KB Output is correct
13 Correct 119 ms 53704 KB Output is correct
14 Correct 88 ms 50372 KB Output is correct
15 Correct 103 ms 47556 KB Output is correct
16 Incorrect 193 ms 54864 KB Output isn't correct
17 Halted 0 ms 0 KB -