oj.uz

Submission #1077811

# Submission time Handle Problem Language Result Execution time Memory
1077811 2024-08-27T09:20:24 Z GrindMachine Swapping Cities (APIO20_swap) C++17
6 / 100
 116 ms 23432 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<pii> vals[N];
vector<int> best(N,inf1);

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

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

vector<int> pbest(N,inf1);

void dfs4(int u){
    sort(all(vals[u]));
    for(auto [v,w] : adj1[u]){
        amin(pbest[v],max(pbest[u],w));
        for(auto [val,child] : vals[u]){
            if(v == child) conts;
            amin(pbest[v],max(val,w));
            break;
        }

        dfs4(v);
    }
}

int mxweight;
bool is_line = false;

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});
        amax(mxweight,w);
    }

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

    rep(i,n){
        if(sz(adj1[i]) == 1){
            is_line = true;
        }
    }

    return;

    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);
    dfs4(0);

    rep(i,n) amin(best[i],pbest[i]);
}

int getMinimumFuelCapacity(int u, int v) {
    if(is_line) return -1;
    else return mxweight;

    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){
        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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9308 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Correct 4 ms 9304 KB Output is correct
4 Correct 4 ms 9304 KB Output is correct
5 Correct 5 ms 9484 KB Output is correct
6 Correct 5 ms 9308 KB Output is correct
7 Correct 6 ms 9560 KB Output is correct
8 Correct 6 ms 9528 KB Output is correct
9 Correct 36 ms 17016 KB Output is correct
10 Correct 45 ms 18888 KB Output is correct
11 Correct 51 ms 18760 KB Output is correct
12 Correct 47 ms 19396 KB Output is correct
13 Correct 46 ms 19524 KB Output is correct
14 Correct 40 ms 17480 KB Output is correct
15 Correct 75 ms 22760 KB Output is correct
16 Correct 85 ms 22600 KB Output is correct
17 Correct 97 ms 23108 KB Output is correct
18 Correct 79 ms 23432 KB Output is correct
19 Correct 42 ms 15704 KB Output is correct
20 Correct 82 ms 22596 KB Output is correct
21 Correct 116 ms 22344 KB Output is correct
22 Correct 88 ms 23108 KB Output is correct
23 Correct 112 ms 23368 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9308 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Correct 4 ms 9304 KB Output is correct
4 Correct 4 ms 9304 KB Output is correct
5 Correct 5 ms 9484 KB Output is correct
6 Correct 5 ms 9308 KB Output is correct
7 Correct 6 ms 9560 KB Output is correct
8 Correct 6 ms 9528 KB Output is correct
9 Correct 36 ms 17016 KB Output is correct
10 Correct 45 ms 18888 KB Output is correct
11 Correct 51 ms 18760 KB Output is correct
12 Correct 47 ms 19396 KB Output is correct
13 Correct 46 ms 19524 KB Output is correct
14 Correct 40 ms 17480 KB Output is correct
15 Correct 75 ms 22760 KB Output is correct
16 Correct 85 ms 22600 KB Output is correct
17 Correct 97 ms 23108 KB Output is correct
18 Correct 79 ms 23432 KB Output is correct
19 Incorrect 72 ms 22712 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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