oj.uz

Submission #655583

# Submission time Handle Problem Language Result Execution time Memory
655583 2022-11-04T18:46:42 Z urosk Swapping Cities (APIO20_swap) C++14
7 / 100
 386 ms 68100 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 500005
#define lg 21
ll n,m;
vector<ll> g[maxn];
struct gr{
    ll x,y,w;
};
bool cmp(gr a,gr b){return a.w<b.w;}
vector<gr> edge;
ll c[maxn];
bool ok[maxn];
ll dsu[maxn];
ll deg[maxn];
ll in[maxn];
ll out[maxn];
ll it;
ll root(ll x){
    while(x!=dsu[x]){
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}
ll st[maxn][lg];
ll oke[maxn][lg];
vector<pll> v;
void upd(ll x,ll y,ll w){
    deg[x]++; deg[y]++;
    bool f = (deg[x]>=3)||(deg[y]>=3);
    x = root(x); y = root(y);
    ++it;
    if(x==y){
        g[x].pb(it);
        g[it].pb(x);
        v.pb({it,x});
        ok[it] = 1;
        dsu[x] = it;
    }else{
        g[x].pb(it);
        g[it].pb(x);
        g[y].pb(it);
        g[it].pb(y);
        v.pb({it,x});
        v.pb({it,y});
        ok[it] = ok[x]|ok[y]|f;
        dsu[x] = dsu[y] = it;
    }
    c[it] = w;
}
ll itr = 0;
void dfs(ll u,ll p){
    st[u][0] = p;
    oke[u][0] = ok[p];
    in[u] = ++itr;
    for(ll s : g[u]){
        if(s==p) continue;
        dfs(s,u);
    }
    out[u] = itr;
}
bool intree(ll x,ll y){
    return in[y]<=in[x]&&out[x]<=out[y];
}
ll lca(ll x,ll y){
    if(intree(y,x)) return x;
    if(intree(x,y)) return y;
    for(ll j = lg-1;j>=0;j--){
        if(!intree(x,st[y][j])) y = st[y][j];
    }
    return st[y][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N; m = M;
    it = n;
    iota(dsu+1,dsu+maxn,1);
    for(ll i = 0;i<m;i++){
        ll x = U[i]; ll y = V[i]; ll w = W[i];
        ++x; ++y;
        edge.pb({x,y,w});
    }
    sort(all(edge),cmp);
    for(gr e : edge){
        ll x = e.x; ll y = e.y; ll w = e.w;
        upd(x,y,w);
    }
    dfs(it,it);
    for(ll j = 1;j<lg;j++){
        for(ll i = 1;i<=it;i++) st[i][j] = st[st[i][j-1]][j-1];
    }
    for(ll j = 1;j<lg;j++){
        for(ll i = 1;i<=it;i++) oke[i][j] = oke[i][j-1]|oke[st[st[i][j-1]][0]][j-1];
    }
}
int getMinimumFuelCapacity(int X, int Y) {
    ll x = X; ll y = Y;
    ++x; ++y;
    ll z = lca(x,y);
    if(ok[z]) return c[z];
    for(ll j = lg-1;j>=0;j--){
        if(!oke[z][j]) z = st[z][j];
    }
    z = st[z][0];
    ll ans = c[z];
    if(ok[z]==0) ans = -1;
    return ans;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14036 KB Output is correct
4 Correct 8 ms 14164 KB Output is correct
5 Correct 8 ms 14380 KB Output is correct
6 Correct 8 ms 14472 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 167 ms 50724 KB Output is correct
10 Correct 195 ms 58860 KB Output is correct
11 Correct 192 ms 58080 KB Output is correct
12 Correct 214 ms 60720 KB Output is correct
13 Correct 222 ms 62992 KB Output is correct
14 Correct 172 ms 50744 KB Output is correct
15 Correct 300 ms 60924 KB Output is correct
16 Correct 292 ms 59688 KB Output is correct
17 Correct 303 ms 62452 KB Output is correct
18 Correct 386 ms 64740 KB Output is correct
19 Incorrect 94 ms 24456 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 7 ms 14036 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 341 ms 65672 KB Output is correct
4 Correct 331 ms 68100 KB Output is correct
5 Correct 341 ms 66560 KB Output is correct
6 Correct 347 ms 67888 KB Output is correct
7 Correct 342 ms 67344 KB Output is correct
8 Correct 335 ms 65252 KB Output is correct
9 Correct 367 ms 66948 KB Output is correct
10 Correct 329 ms 64688 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14036 KB Output is correct
4 Correct 8 ms 14164 KB Output is correct
5 Correct 8 ms 14380 KB Output is correct
6 Correct 8 ms 14472 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 7 ms 14036 KB Output is correct
10 Correct 9 ms 14420 KB Output is correct
11 Correct 8 ms 14504 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Incorrect 8 ms 14420 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14036 KB Output is correct
4 Correct 7 ms 14036 KB Output is correct
5 Correct 8 ms 14164 KB Output is correct
6 Correct 8 ms 14380 KB Output is correct
7 Correct 8 ms 14472 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 167 ms 50724 KB Output is correct
11 Correct 195 ms 58860 KB Output is correct
12 Correct 192 ms 58080 KB Output is correct
13 Correct 214 ms 60720 KB Output is correct
14 Correct 222 ms 62992 KB Output is correct
15 Correct 9 ms 14420 KB Output is correct
16 Correct 8 ms 14504 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Incorrect 8 ms 14420 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14036 KB Output is correct
4 Correct 8 ms 14164 KB Output is correct
5 Correct 8 ms 14380 KB Output is correct
6 Correct 8 ms 14472 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 167 ms 50724 KB Output is correct
10 Correct 195 ms 58860 KB Output is correct
11 Correct 192 ms 58080 KB Output is correct
12 Correct 214 ms 60720 KB Output is correct
13 Correct 222 ms 62992 KB Output is correct
14 Correct 172 ms 50744 KB Output is correct
15 Correct 300 ms 60924 KB Output is correct
16 Correct 292 ms 59688 KB Output is correct
17 Correct 303 ms 62452 KB Output is correct
18 Correct 386 ms 64740 KB Output is correct
19 Correct 341 ms 65672 KB Output is correct
20 Correct 331 ms 68100 KB Output is correct
21 Correct 341 ms 66560 KB Output is correct
22 Correct 347 ms 67888 KB Output is correct
23 Correct 342 ms 67344 KB Output is correct
24 Correct 335 ms 65252 KB Output is correct
25 Correct 367 ms 66948 KB Output is correct
26 Correct 329 ms 64688 KB Output is correct
27 Correct 9 ms 14420 KB Output is correct
28 Correct 8 ms 14504 KB Output is correct
29 Correct 8 ms 14420 KB Output is correct
30 Correct 8 ms 14420 KB Output is correct
31 Correct 8 ms 14420 KB Output is correct
32 Incorrect 8 ms 14420 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14036 KB Output is correct
4 Correct 7 ms 14036 KB Output is correct
5 Correct 8 ms 14164 KB Output is correct
6 Correct 8 ms 14380 KB Output is correct
7 Correct 8 ms 14472 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 167 ms 50724 KB Output is correct
11 Correct 195 ms 58860 KB Output is correct
12 Correct 192 ms 58080 KB Output is correct
13 Correct 214 ms 60720 KB Output is correct
14 Correct 222 ms 62992 KB Output is correct
15 Correct 172 ms 50744 KB Output is correct
16 Correct 300 ms 60924 KB Output is correct
17 Correct 292 ms 59688 KB Output is correct
18 Correct 303 ms 62452 KB Output is correct
19 Correct 386 ms 64740 KB Output is correct
20 Correct 341 ms 65672 KB Output is correct
21 Correct 331 ms 68100 KB Output is correct
22 Correct 341 ms 66560 KB Output is correct
23 Correct 347 ms 67888 KB Output is correct
24 Correct 342 ms 67344 KB Output is correct
25 Correct 335 ms 65252 KB Output is correct
26 Correct 367 ms 66948 KB Output is correct
27 Correct 329 ms 64688 KB Output is correct
28 Correct 9 ms 14420 KB Output is correct
29 Correct 8 ms 14504 KB Output is correct
30 Correct 8 ms 14420 KB Output is correct
31 Correct 8 ms 14420 KB Output is correct
32 Correct 8 ms 14420 KB Output is correct
33 Incorrect 8 ms 14420 KB Output isn't correct
34 Halted 0 ms 0 KB -