oj.uz

Submission #1077799

# Submission time Handle Problem Language Result Execution time Memory
1077799 2024-08-27T09:12:14 Z GrindMachine Swapping Cities (APIO20_swap) C++17
0 / 100
 305 ms 53824 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define ff first
#define ss second

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
    return "'"+s+"'";
}

string to_string(const char* s){
    return to_string((string)s);
}

string to_string(bool b){
    return b?"true":"false";
}

string to_string(vector<bool> v){
    string res = "{";
    rep(i,sz(v)){
        res += to_string(v[i])+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "swap.h"

vector<int> par(N);

int find(int u){
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    par[v] = u;
}

vector<pii> adj1[N], adj2[N];
vector<int> pedge(N,inf1);

void dfs1(int u, int p){
    for(auto [v,w] : adj1[u]){
        if(v == p) conts;
        pedge[v] = w;
        pii px = {u,w};
        adj1[v].erase(find(all(adj1[v]),px));
        dfs1(v,u);
    }
}

int fmn(int u, pii ignore){
    for(auto [w,v] : adj2[u]){
        if(v == ignore.ff or v == ignore.ss) conts;
        return w;
    }
    return inf1;
}

const int LOG = 17;

int up[N][LOG], mnw[N][LOG], mxw[N][LOG];
vector<int> depth(N);

void dfs2(int u){
    for(auto [v,w] : adj1[u]){
        depth[v] = depth[u]+1;
        up[v][0] = u;
        mnw[v][0] = fmn(u,{v,-1});
        mxw[v][0] = w;
        rep1(j,LOG-1){
            up[v][j] = up[up[v][j-1]][j-1];
            mnw[v][j] = min(mnw[v][j-1],mnw[up[v][j-1]][j-1]);
            mxw[v][j] = max(mxw[v][j-1],mxw[up[v][j-1]][j-1]);
        }

        dfs2(v);
    }
}

int lift(int u, int k){
    rep(j,LOG){
        if(k&(1<<j)){
            u = up[u][j];
        }
    }
    return u;
}

int get_lca(int u, int v){
    if(depth[u] < depth[v]) swap(u,v);
    int k = depth[u]-depth[v];
    u = lift(u,k);
    if(u == v) return u;

    rev(j,LOG-1,0){
        if(up[u][j] != up[v][j]){
            u = up[u][j];
            v = up[v][j];
        }
    }

    u = up[u][0], v = up[v][0];
    assert(u == v);
    return u;
}

int get_mn(int u, int k){
    if(k < 0) return inf1;
    int mn = inf1;
    rep(j,LOG){
        if(k&(1<<j)){
            amin(mn,mnw[u][j]);
            u = up[u][j];
        }
    }
    return mn;
}

int get_mx(int u, int k){
    int mx = -inf1;
    rep(j,LOG){
        if(k&(1<<j)){
            amax(mx,mxw[u][j]);
            u = up[u][j];
        }
    }
    return mx;
}

vector<int> vals[N];
vector<int> best(N,inf1);

void dfs3(int u){
    vector<int> weights;
    for(auto [v,w] : adj1[u]){
        dfs3(v);
        amin(best[u],max(best[v],w));
        weights.pb(w);
    }

    if(sz(weights) >= 2){
        amin(best[u],weights[1]);
    }
}

void dfs4(int u){
    for(auto [v,w] : adj1[u]){


        dfs4(v);
    }
}

void init(int n, int m,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    vector<array<int,3>> edges;
    rep(i,m){
        edges.pb({W[i],U[i],V[i]});
    }

    sort(all(edges));
    vector<array<int,3>> span, non_span;
    iota(all(par),0);

    for(auto [w,u,v] : edges){
        if(find(u) != find(v)){
            span.pb({u,v,w});
            merge(u,v);
        }
        else{
            non_span.pb({u,v,w});
        }
    }

    for(auto [u,v,w] : span){
        adj1[u].pb({v,w}), adj1[v].pb({u,w});
    }

    for(auto [u,v,w] : non_span){
        adj2[u].pb({w,v}), adj2[v].pb({w,v});
    }

    dfs1(0,-1);

    rep(u,n){
        for(auto [v,w] : adj1[u]){
            adj2[u].pb({w,v});
        }

        sort(all(adj1[u]));
        sort(all(adj2[u]));
    }

    rep(j,LOG) mnw[0][j] = inf1;
    dfs2(0);

    dfs3(0);
    rep(i,n) vals[i].pb(inf1), vals[i].pb(inf1);
}

int getMinimumFuelCapacity(int u, int v) {
    if(depth[u] > depth[v]) swap(u,v);
    int lca = get_lca(u,v);

    int du = depth[u]-depth[lca];
    int dv = depth[v]-depth[lca];
    int pmx = max(get_mx(u,du),get_mx(v,dv));

    int mn = inf1;
    amin(mn,get_mn(u,du-1));
    amin(mn,get_mn(v,dv-1));

    if(u == lca){
        amin(mn,best[v]);
    }
    else{
        int jbu = lift(u,du-1), jbv = lift(v,dv-1);
        amin(mn,fmn(lca,{jbu,jbv}));
        amin(mn,pedge[lca]);
        amin(mn,best[u]);
        amin(mn,best[v]);
    }

    int ans = max(pmx,mn);
    if(ans == inf1) ans = -1;

    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9052 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 5 ms 9404 KB Output is correct
6 Correct 5 ms 9308 KB Output is correct
7 Correct 4 ms 9328 KB Output is correct
8 Correct 5 ms 9304 KB Output is correct
9 Correct 97 ms 40232 KB Output is correct
10 Correct 124 ms 48708 KB Output is correct
11 Correct 119 ms 47540 KB Output is correct
12 Correct 138 ms 49984 KB Output is correct
13 Correct 118 ms 52292 KB Output is correct
14 Correct 148 ms 39564 KB Output is correct
15 Correct 290 ms 50248 KB Output is correct
16 Correct 305 ms 47172 KB Output is correct
17 Correct 256 ms 53824 KB Output is correct
18 Correct 297 ms 51988 KB Output is correct
19 Incorrect 92 ms 17752 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9052 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 5 ms 9404 KB Output is correct
6 Correct 5 ms 9308 KB Output is correct
7 Correct 4 ms 9328 KB Output is correct
8 Correct 5 ms 9304 KB Output is correct
9 Incorrect 4 ms 9052 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9052 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 4 ms 9052 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 5 ms 9404 KB Output is correct
6 Correct 5 ms 9308 KB Output is correct
7 Correct 4 ms 9328 KB Output is correct
8 Correct 5 ms 9304 KB Output is correct
9 Correct 97 ms 40232 KB Output is correct
10 Correct 124 ms 48708 KB Output is correct
11 Correct 119 ms 47540 KB Output is correct
12 Correct 138 ms 49984 KB Output is correct
13 Correct 118 ms 52292 KB Output is correct
14 Correct 148 ms 39564 KB Output is correct
15 Correct 290 ms 50248 KB Output is correct
16 Correct 305 ms 47172 KB Output is correct
17 Correct 256 ms 53824 KB Output is correct
18 Correct 297 ms 51988 KB Output is correct
19 Incorrect 145 ms 41284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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