oj.uz

Submission #655584

# Submission time Handle Problem Language Result Execution time Memory
655584 2022-11-04T18:47:31 Z urosk Swapping Cities (APIO20_swap) C++14
7 / 100
 530 ms 97620 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 1000005
#define lg 31
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 14 ms 27732 KB Output is correct
2 Correct 15 ms 27764 KB Output is correct
3 Correct 14 ms 27732 KB Output is correct
4 Correct 17 ms 28012 KB Output is correct
5 Correct 15 ms 28284 KB Output is correct
6 Correct 15 ms 28324 KB Output is correct
7 Correct 15 ms 28256 KB Output is correct
8 Correct 15 ms 28308 KB Output is correct
9 Correct 225 ms 76684 KB Output is correct
10 Correct 297 ms 87616 KB Output is correct
11 Correct 259 ms 86588 KB Output is correct
12 Correct 312 ms 90212 KB Output is correct
13 Correct 291 ms 92436 KB Output is correct
14 Correct 274 ms 76788 KB Output is correct
15 Correct 392 ms 89864 KB Output is correct
16 Correct 422 ms 88192 KB Output is correct
17 Correct 390 ms 91772 KB Output is correct
18 Correct 530 ms 94176 KB Output is correct
19 Incorrect 119 ms 40628 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 14 ms 27732 KB Output is correct
2 Correct 15 ms 27764 KB Output is correct
3 Correct 445 ms 94152 KB Output is correct
4 Correct 452 ms 97620 KB Output is correct
5 Correct 445 ms 95296 KB Output is correct
6 Correct 453 ms 97232 KB Output is correct
7 Correct 475 ms 96360 KB Output is correct
8 Correct 438 ms 93664 KB Output is correct
9 Correct 438 ms 95860 KB Output is correct
10 Correct 460 ms 92988 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27732 KB Output is correct
2 Correct 15 ms 27764 KB Output is correct
3 Correct 14 ms 27732 KB Output is correct
4 Correct 17 ms 28012 KB Output is correct
5 Correct 15 ms 28284 KB Output is correct
6 Correct 15 ms 28324 KB Output is correct
7 Correct 15 ms 28256 KB Output is correct
8 Correct 15 ms 28308 KB Output is correct
9 Correct 14 ms 27660 KB Output is correct
10 Correct 15 ms 28372 KB Output is correct
11 Correct 14 ms 28380 KB Output is correct
12 Correct 14 ms 28300 KB Output is correct
13 Correct 15 ms 28200 KB Output is correct
14 Correct 15 ms 28228 KB Output is correct
15 Incorrect 15 ms 28308 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27660 KB Output is correct
2 Correct 14 ms 27732 KB Output is correct
3 Correct 15 ms 27764 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 17 ms 28012 KB Output is correct
6 Correct 15 ms 28284 KB Output is correct
7 Correct 15 ms 28324 KB Output is correct
8 Correct 15 ms 28256 KB Output is correct
9 Correct 15 ms 28308 KB Output is correct
10 Correct 225 ms 76684 KB Output is correct
11 Correct 297 ms 87616 KB Output is correct
12 Correct 259 ms 86588 KB Output is correct
13 Correct 312 ms 90212 KB Output is correct
14 Correct 291 ms 92436 KB Output is correct
15 Correct 15 ms 28372 KB Output is correct
16 Correct 14 ms 28380 KB Output is correct
17 Correct 14 ms 28300 KB Output is correct
18 Correct 15 ms 28200 KB Output is correct
19 Correct 15 ms 28228 KB Output is correct
20 Incorrect 15 ms 28308 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27732 KB Output is correct
2 Correct 15 ms 27764 KB Output is correct
3 Correct 14 ms 27732 KB Output is correct
4 Correct 17 ms 28012 KB Output is correct
5 Correct 15 ms 28284 KB Output is correct
6 Correct 15 ms 28324 KB Output is correct
7 Correct 15 ms 28256 KB Output is correct
8 Correct 15 ms 28308 KB Output is correct
9 Correct 225 ms 76684 KB Output is correct
10 Correct 297 ms 87616 KB Output is correct
11 Correct 259 ms 86588 KB Output is correct
12 Correct 312 ms 90212 KB Output is correct
13 Correct 291 ms 92436 KB Output is correct
14 Correct 274 ms 76788 KB Output is correct
15 Correct 392 ms 89864 KB Output is correct
16 Correct 422 ms 88192 KB Output is correct
17 Correct 390 ms 91772 KB Output is correct
18 Correct 530 ms 94176 KB Output is correct
19 Correct 445 ms 94152 KB Output is correct
20 Correct 452 ms 97620 KB Output is correct
21 Correct 445 ms 95296 KB Output is correct
22 Correct 453 ms 97232 KB Output is correct
23 Correct 475 ms 96360 KB Output is correct
24 Correct 438 ms 93664 KB Output is correct
25 Correct 438 ms 95860 KB Output is correct
26 Correct 460 ms 92988 KB Output is correct
27 Correct 15 ms 28372 KB Output is correct
28 Correct 14 ms 28380 KB Output is correct
29 Correct 14 ms 28300 KB Output is correct
30 Correct 15 ms 28200 KB Output is correct
31 Correct 15 ms 28228 KB Output is correct
32 Incorrect 15 ms 28308 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27660 KB Output is correct
2 Correct 14 ms 27732 KB Output is correct
3 Correct 15 ms 27764 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 17 ms 28012 KB Output is correct
6 Correct 15 ms 28284 KB Output is correct
7 Correct 15 ms 28324 KB Output is correct
8 Correct 15 ms 28256 KB Output is correct
9 Correct 15 ms 28308 KB Output is correct
10 Correct 225 ms 76684 KB Output is correct
11 Correct 297 ms 87616 KB Output is correct
12 Correct 259 ms 86588 KB Output is correct
13 Correct 312 ms 90212 KB Output is correct
14 Correct 291 ms 92436 KB Output is correct
15 Correct 274 ms 76788 KB Output is correct
16 Correct 392 ms 89864 KB Output is correct
17 Correct 422 ms 88192 KB Output is correct
18 Correct 390 ms 91772 KB Output is correct
19 Correct 530 ms 94176 KB Output is correct
20 Correct 445 ms 94152 KB Output is correct
21 Correct 452 ms 97620 KB Output is correct
22 Correct 445 ms 95296 KB Output is correct
23 Correct 453 ms 97232 KB Output is correct
24 Correct 475 ms 96360 KB Output is correct
25 Correct 438 ms 93664 KB Output is correct
26 Correct 438 ms 95860 KB Output is correct
27 Correct 460 ms 92988 KB Output is correct
28 Correct 15 ms 28372 KB Output is correct
29 Correct 14 ms 28380 KB Output is correct
30 Correct 14 ms 28300 KB Output is correct
31 Correct 15 ms 28200 KB Output is correct
32 Correct 15 ms 28228 KB Output is correct
33 Incorrect 15 ms 28308 KB Output isn't correct
34 Halted 0 ms 0 KB -