oj.uz

Submission #975346

# Submission time Handle Problem Language Result Execution time Memory
975346 2024-05-04T22:43:16 Z imarn Swapping Cities (APIO20_swap) C++14
6 / 100
 232 ms 29660 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=1e5+5;
struct segment{
    int t[2*mxn]{0};
    void upd(int i,int amt,int sz){
        i+=sz;t[i]=amt;
        for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
    }
    int qr(int l,int r,int sz,int rs=0){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)rs=max(rs,t[l++]);
            if(r&1)rs=max(rs,t[--r]);
        }return rs;
    }
}seg;
struct lazy{
    int t[4*mxn]{0},lz[4*mxn]{0};
    void build(){
        for(int i=0;i<4*mxn;i++)t[i]=lz[i]=2e9;
    }
    void push(int i,int l,int r){
        t[i]=min(t[i],lz[i]);
        if(l<r)lz[2*i]=min(lz[2*i],lz[i]),lz[2*i+1]=min(lz[2*i+1],lz[i]);
        lz[i]=2e9;
    }
    void upd(int i,int l,int r,int tl,int tr,int v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]=min(lz[i],v);push(i,l,r);return;
        }int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
        t[i]=min(t[2*i],t[2*i+1]);
    }
    int qr(int i,int l,int r,int tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return 2e9;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
    }
}lseg;
vector<pii>g[mxn];
int up[mxn]{0},pr[mxn]{0},dep[mxn]{0},head[mxn]{0},id[mxn]{0},ct=0,sz[mxn]{0},a[mxn]{0},n;
int get(int r){
    return up[r]==r?r:up[r]=get(up[r]);
}
void dfs(int u,int p,int l){
    pr[u]=p;dep[u]=l;sz[u]=1;
    for(auto v:g[u]){
        if(v.f==p)continue;
        dfs(v.f,u,l+1);
        a[v.f]=v.s;sz[u]+=sz[v.f];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++ct;
    int hv=-1,hc=-1;
    for(auto v:g[u]){
        if(v.f!=p&&sz[v.f]>hc)hc=sz[v.f],hv=v.f;
    }
    if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v.f==p||v.f==hv)continue;
        hld(v.f,u,v.f);
    }
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n=N;vector<pair<int,pii>>ed,bin;for(int i=0;i<N;i++)up[i]=i;
    for(int i=0;i<M;i++)ed.pb({W[i],{U[i],V[i]}});
    sort(ed.begin(),ed.end());
    for(auto it : ed){
        int u=get(it.s.f),v=get(it.s.s);
        if(u==v){bin.pb(it);continue;}
        up[u]=v;g[it.s.f].pb({it.s.s,it.f});
        g[it.s.s].pb({it.s.f,it.f});
    }dfs(0,0,0);hld(0,0,0);for(int i=0;i<N;i++)seg.upd(id[i]-1,a[i],N);
    lseg.build();
    for(auto it : bin){
        int u=it.s.f,v=it.s.s;
        while(head[u]!=head[v]){
            if(dep[head[u]]<dep[head[v]])swap(u,v);
            lseg.upd(1,1,N,id[head[u]],id[u],it.f);
            u=pr[head[u]];
        }
        if(dep[u]>dep[v])swap(u,v);
        lseg.upd(1,1,N,id[u]+1,id[v],it.f);
    }
}
int getMinimumFuelCapacity(int X, int Y){
    int rs1=0,rs2=2e9,x=X,y=Y;
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        rs1=max(rs1,seg.qr(id[head[x]]-1,id[x],n));
        rs2=min(rs2,lseg.qr(1,1,n,id[head[x]],id[x]));
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    rs1=max(rs1,seg.qr(id[x],id[y],n));
    rs2=min(rs2,lseg.qr(1,1,n,id[x]+1,id[y]));
    if(rs2==2e9)return -1;
    return max(rs1,rs2);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8800 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 46 ms 19908 KB Output is correct
10 Correct 58 ms 23748 KB Output is correct
11 Correct 58 ms 22984 KB Output is correct
12 Correct 79 ms 24264 KB Output is correct
13 Correct 58 ms 25800 KB Output is correct
14 Correct 61 ms 19436 KB Output is correct
15 Correct 216 ms 27336 KB Output is correct
16 Correct 232 ms 25368 KB Output is correct
17 Correct 205 ms 29660 KB Output is correct
18 Correct 208 ms 28200 KB Output is correct
19 Correct 108 ms 16216 KB Output is correct
20 Correct 213 ms 26568 KB Output is correct
21 Correct 220 ms 25740 KB Output is correct
22 Correct 227 ms 27792 KB Output is correct
23 Correct 216 ms 28176 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8800 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 195 ms 21704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8800 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Incorrect 2 ms 8540 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8800 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 46 ms 19908 KB Output is correct
11 Correct 58 ms 23748 KB Output is correct
12 Correct 58 ms 22984 KB Output is correct
13 Correct 79 ms 24264 KB Output is correct
14 Correct 58 ms 25800 KB Output is correct
15 Incorrect 2 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8800 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 46 ms 19908 KB Output is correct
10 Correct 58 ms 23748 KB Output is correct
11 Correct 58 ms 22984 KB Output is correct
12 Correct 79 ms 24264 KB Output is correct
13 Correct 58 ms 25800 KB Output is correct
14 Correct 61 ms 19436 KB Output is correct
15 Correct 216 ms 27336 KB Output is correct
16 Correct 232 ms 25368 KB Output is correct
17 Correct 205 ms 29660 KB Output is correct
18 Correct 208 ms 28200 KB Output is correct
19 Incorrect 195 ms 21704 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8800 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 46 ms 19908 KB Output is correct
11 Correct 58 ms 23748 KB Output is correct
12 Correct 58 ms 22984 KB Output is correct
13 Correct 79 ms 24264 KB Output is correct
14 Correct 58 ms 25800 KB Output is correct
15 Correct 61 ms 19436 KB Output is correct
16 Correct 216 ms 27336 KB Output is correct
17 Correct 232 ms 25368 KB Output is correct
18 Correct 205 ms 29660 KB Output is correct
19 Correct 208 ms 28200 KB Output is correct
20 Incorrect 195 ms 21704 KB Output isn't correct
21 Halted 0 ms 0 KB -