oj.uz

Submission #576579

# Submission time Handle Problem Language Result Execution time Memory
576579 2022-06-13T08:11:05 Z radal Swapping Cities (APIO20_swap) C++17
0 / 100
 268 ms 35936 KB 
#include <bits/stdc++.h>
#include "swap.h"
#pragma GCC target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
//    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
vector<int> pr[N],comp[N],adj[N];
int mi[N],n,m;
vector<pair<int,pll> > e;
void init (int nn,int mm,vector<int> U,vector<int> V,vector<int> W){
    n = nn;
    m = mm;
    rep(i,1,n+1){
        pr[i].pb(i);
        comp[i].pb(i);
        mi[i] = inf;
    }
    rep(i,0,m){
        U[i]++;
        V[i]++;
        e.pb({W[i],{U[i],V[i]}});
    }
    sort(all(e));
    rep(i,0,m){
        int x = e[i].Y.X,y = e[i].Y.Y;
        int u = pr[x].back(),v = pr[y].back();
        if (u != v){
            adj[x].pb(y);
            adj[y].pb(x);
            if (comp[u].size() > comp[v].size()) swap(u,v);
            while (!comp[u].empty()){
                int w = comp[u].back();
                comp[u].pop_back();
                pr[w].pb(v);
                comp[v].pb(w);
            }
            if (mi[u] < inf) mi[v] = min(mi[v],e[i].X);
            if (adj[x].size() >= 3 || adj[y].size() >= 3) mi[v] = min(mi[v],e[i].X);
        }
        else{
            mi[u] = min(mi[u],e[i].X);
        }
    }
}
int getMinimumFuelCapacity(int u, int v){
    u++;
    v++;
    int po1 = pr[u].size()-1,po2 = pr[v].size()-1;
    while (min(po1,po2) >= 1 && pr[u][po1-1] == pr[v][po2-1]) po1--,po2--;
    int calc = mi[pr[u][po1]];
    if (calc == inf) return -1;
    return calc;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 7 ms 14404 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 8 ms 14460 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Correct 130 ms 29972 KB Output is correct
10 Correct 194 ms 33056 KB Output is correct
11 Correct 177 ms 32732 KB Output is correct
12 Correct 182 ms 33936 KB Output is correct
13 Correct 130 ms 28624 KB Output is correct
14 Correct 136 ms 29888 KB Output is correct
15 Correct 224 ms 35268 KB Output is correct
16 Correct 268 ms 34580 KB Output is correct
17 Correct 246 ms 35936 KB Output is correct
18 Correct 203 ms 30252 KB Output is correct
19 Incorrect 77 ms 20640 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 7 ms 14404 KB Output is correct
3 Incorrect 152 ms 29700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 7 ms 14404 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 8 ms 14460 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Incorrect 8 ms 14316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 7 ms 14404 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 8 ms 14460 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 9 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Correct 130 ms 29972 KB Output is correct
10 Correct 194 ms 33056 KB Output is correct
11 Correct 177 ms 32732 KB Output is correct
12 Correct 182 ms 33936 KB Output is correct
13 Correct 130 ms 28624 KB Output is correct
14 Correct 136 ms 29888 KB Output is correct
15 Correct 224 ms 35268 KB Output is correct
16 Correct 268 ms 34580 KB Output is correct
17 Correct 246 ms 35936 KB Output is correct
18 Correct 203 ms 30252 KB Output is correct
19 Incorrect 152 ms 29700 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14316 KB Output isn't correct
2 Halted 0 ms 0 KB -