oj.uz

답안 #1077806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077806 2024-08-27T09:16:36 Z GrindMachine 자매 도시 (APIO20_swap) C++17
0 / 100
 320 ms 58576 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);
    }
}

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

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9308 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Correct 6 ms 9468 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 105 ms 42316 KB Output is correct
10 Correct 146 ms 51256 KB Output is correct
11 Correct 133 ms 49984 KB Output is correct
12 Correct 137 ms 52496 KB Output is correct
13 Correct 125 ms 54844 KB Output is correct
14 Correct 123 ms 41800 KB Output is correct
15 Correct 320 ms 55052 KB Output is correct
16 Correct 310 ms 51776 KB Output is correct
17 Correct 268 ms 58576 KB Output is correct
18 Correct 292 ms 57156 KB Output is correct
19 Incorrect 97 ms 20060 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9308 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Incorrect 142 ms 44088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9308 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Correct 6 ms 9468 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Incorrect 4 ms 9304 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 9304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9308 KB Output is correct
2 Correct 4 ms 9308 KB Output is correct
3 Correct 6 ms 9468 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 5 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 105 ms 42316 KB Output is correct
10 Correct 146 ms 51256 KB Output is correct
11 Correct 133 ms 49984 KB Output is correct
12 Correct 137 ms 52496 KB Output is correct
13 Correct 125 ms 54844 KB Output is correct
14 Correct 123 ms 41800 KB Output is correct
15 Correct 320 ms 55052 KB Output is correct
16 Correct 310 ms 51776 KB Output is correct
17 Correct 268 ms 58576 KB Output is correct
18 Correct 292 ms 57156 KB Output is correct
19 Incorrect 142 ms 44088 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 9304 KB Output isn't correct
2 Halted 0 ms 0 KB -