oj.uz

Submission #925265

# Submission time Handle Problem Language Result Execution time Memory
925265 2024-02-11T09:07:03 Z adhityamv Swapping Cities (APIO20_swap) C++17
7 / 100
 131 ms 23128 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int INF=1000000000;
struct UFDS{
    int n;
    vector<vector<pii>> roots;
    vector<vector<int>> children;
    vector<int> siz;
    vector<int> unpath;
    vector<pii> pathpoints;
    UFDS(){
        n=0;
    }
    void dsinit(int nn){
        n=nn;
        for(int i=0;i<n;i++){
            vector<int> v;
            v.push_back(i);
            vector<pii> vv;
            vv.push_back(mp(i,0));
            roots.push_back(vv);
            children.push_back(v);
            siz.push_back(1);
            unpath.push_back(-1);
            pathpoints.push_back(mp(i,i));
        }
    }
    bool unite(int x,int y,int w){
        int ox=x,oy=y;
        x=roots[x].back().first;
        y=roots[y].back().first;
        if(x==y){
            if(unpath[x]==-1){
                unpath[x]=w;
            }
            return false;
        }
        if(siz[x]<siz[y]) swap(x,y);
        for(int i:children[y]){
            roots[i].push_back(mp(x,w));
            children[x].push_back(i);
        }
        siz[x]+=siz[y];
        if(unpath[x]==-1 && unpath[y]==-1){
            if((ox!=pathpoints[x].fi && ox!=pathpoints[x].se) || (oy!=pathpoints[y].fi && oy!=pathpoints[y].se)){
                unpath[x]=w;
            }
            else{
                pathpoints[x]=mp(pathpoints[x].fi+pathpoints[x].se-ox,pathpoints[y].fi+pathpoints[y].se-oy);
            }
        }
        if(unpath[x]==-1 && unpath[y]!=-1) unpath[x]=w;
        return true;
    }
};
UFDS ds;
bool ispath=false;
void init(int n,int m,vector<int> u,vector<int> v,vector<int> w){
    vector<pair<int,pii>> edges;
    for(int i=0;i<m;i++) edges.push_back(mp(w[i],mp(u[i],v[i])));
    sort(edges.begin(),edges.end());
    ds.dsinit(n);
    for(auto p:edges){
        ds.unite(p.se.fi,p.se.se,p.fi);
    }
    if(ds.unpath[ds.roots[0].back().fi]==-1) ispath=true;
}
int getMinimumFuelCapacity(int u,int v){
    if(ispath) return -1;
    int iu=ds.roots[u].size()-1;
    int iv=ds.roots[v].size()-1;
    while(ds.roots[u][iu].fi==ds.roots[v][iv].fi){
        iu--,iv--;
    }
    iu++,iv++;
    while(ds.unpath[ds.roots[u][iu].fi]==-1) iu++;
    return max(max(ds.roots[u][iu].se,ds.roots[v][iv].se),ds.unpath[ds.roots[u][iu].fi]);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Incorrect 1 ms 348 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 99 ms 22848 KB Output is correct
4 Correct 102 ms 22796 KB Output is correct
5 Correct 102 ms 22840 KB Output is correct
6 Correct 100 ms 23032 KB Output is correct
7 Correct 104 ms 22968 KB Output is correct
8 Correct 100 ms 22820 KB Output is correct
9 Correct 131 ms 23128 KB Output is correct
10 Correct 96 ms 22784 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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