oj.uz

Submission #566216

# Submission time Handle Problem Language Result Execution time Memory
566216 2022-05-22T06:49:17 Z zaneyu Swapping Cities (APIO20_swap) C++14
7 / 100
 269 ms 24412 KB 
/*input
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

*/
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
#define MXTO(a,b) a=max(a,b)
#define MNTO(a,b) a=min(a,b)
#define sz(x) (int)x.size()
#define pb push_back
const int maxn=1e5+5;
vector<pair<int,pii>> ed;
int n,m;
int par[maxn];
pair<bool,pii> cmp[maxn];
vector<int> vv[maxn];
int find(int u){
    if(par[u]==u) return u;
    return par[u]=find(par[u]);
}
vector<pii> sp[maxn];
int sc[maxn];
const int INF=0x3f3f3f3f;
void merge(int t,int a,int b){
    int oa=a,ob=b;
    a=find(a),b=find(b);
    if(a==b){
        if(sc[a]==INF) sc[a]=t;
        cmp[a].f=0;
        return;
    }
    if(sz(vv[a])<sz(vv[b])) swap(a,b);
    par[b]=a;
    if(cmp[a].f and cmp[b].f){
        if((oa==cmp[a].s.f or oa==cmp[a].s.s) and (ob==cmp[b].s.f or ob==cmp[b].s.s)){
            cmp[a].f=1;
            if(oa==cmp[a].s.f) cmp[a].s.f=cmp[a].s.s;
            if(ob==cmp[b].s.f) cmp[a].s.s=cmp[b].s.s;
            else cmp[a].s.s=cmp[b].s.f;
        }
        else{
            if(sc[a]==INF) sc[a]=t;
            cmp[a].f=0;
        }
    }
    else{
        if(sc[a]==INF) sc[a]=t;
        cmp[a].f=0;
    }
    for(int x:vv[b]) sp[x].pb({t,a}),vv[a].pb(x);
    vv[b].clear();
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N,m=M;
    REP(i,M){
        ed.pb({W[i],{U[i],V[i]}});
    }
    sort(ALL(ed));
    REP(i,n) par[i]=i,cmp[i]={1,{i,i}},vv[i].pb(i),sc[i]=INF,sp[i].pb({-1,i});
    REP(i,m){
        auto a=ed[i];
        merge(i,a.s.f,a.s.s);
    }
}
int gp(int x,int t){
    return (*prev(upper_bound(ALL(sp[x]),make_pair(t,INF)))).s;
}
int getMinimumFuelCapacity(int x, int y) {
    int l=0,r=m-1;
    int a=gp(x,m-1),b=gp(y,m-1);
    if(a!=b or sc[a]==INF){
        return -1;
    }
    while(l<r){
        int mid=(l+r)/2;
        int a=gp(x,mid),b=gp(y,mid);
        if(a==b and sc[a]<=mid) r=mid;
        else l=mid+1;
    }
    return ed[l].f;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 230 ms 19952 KB Output is correct
4 Correct 239 ms 24268 KB Output is correct
5 Correct 213 ms 24292 KB Output is correct
6 Correct 195 ms 24188 KB Output is correct
7 Correct 269 ms 24412 KB Output is correct
8 Correct 213 ms 23852 KB Output is correct
9 Correct 232 ms 24088 KB Output is correct
10 Correct 198 ms 23664 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -