oj.uz

Submission #975347

# Submission time Handle Problem Language Result Execution time Memory
975347 2024-05-04T22:44:41 Z imarn Swapping Cities (APIO20_swap) C++14
0 / 100
 197 ms 25184 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 -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 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 8552 KB Output is correct
6 Correct 2 ms 8700 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 46 ms 18120 KB Output is correct
10 Correct 58 ms 21680 KB Output is correct
11 Correct 58 ms 20936 KB Output is correct
12 Correct 61 ms 21956 KB Output is correct
13 Correct 61 ms 23748 KB Output is correct
14 Correct 58 ms 17512 KB Output is correct
15 Correct 197 ms 22980 KB Output is correct
16 Correct 197 ms 20936 KB Output is correct
17 Correct 185 ms 25184 KB Output is correct
18 Correct 181 ms 23748 KB Output is correct
19 Incorrect 97 ms 13140 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 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 8552 KB Output is correct
6 Correct 2 ms 8700 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Incorrect 2 ms 8536 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 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 8552 KB Output is correct
6 Correct 2 ms 8700 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 46 ms 18120 KB Output is correct
10 Correct 58 ms 21680 KB Output is correct
11 Correct 58 ms 20936 KB Output is correct
12 Correct 61 ms 21956 KB Output is correct
13 Correct 61 ms 23748 KB Output is correct
14 Correct 58 ms 17512 KB Output is correct
15 Correct 197 ms 22980 KB Output is correct
16 Correct 197 ms 20936 KB Output is correct
17 Correct 185 ms 25184 KB Output is correct
18 Correct 181 ms 23748 KB Output is correct
19 Incorrect 181 ms 17752 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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