oj.uz

Submission #1077568

# Submission time Handle Problem Language Result Execution time Memory
1077568 2024-08-27T08:03:12 Z GrindMachine Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 52296 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){
    int mn = inf1;
    for(auto [v,w] : adj2[u]){
        if(v == ignore.ff or v == ignore.ss) conts;
        amin(mn,w);
    }
    return mn;
}

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;
}

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({v,w}), adj2[v].pb({u,w});
    }

    dfs1(0,-1);

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

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

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

int getMinimumFuelCapacity(int u, int v) {
    return -1;

    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 jb = lift(v,dv-1);
        // amin(mn,fmn(u,{jb,-1}));
    }
    else{
        amin(mn,fmn(u,{-1,-1}));
        int jbu = lift(u,du-1), jbv = lift(v,dv-1);
        amin(mn,fmn(lca,{jbu,jbv}));
        amin(mn,pedge[lca]);
    }

    amin(mn,fmn(v,{-1,-1}));

    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 6236 KB Output is correct
2 Correct 3 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 4 ms 6488 KB Output is correct
5 Correct 4 ms 6488 KB Output is correct
6 Correct 3 ms 6504 KB Output is correct
7 Correct 4 ms 6488 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 95 ms 36544 KB Output is correct
10 Correct 116 ms 45056 KB Output is correct
11 Correct 136 ms 43888 KB Output is correct
12 Correct 136 ms 46380 KB Output is correct
13 Correct 131 ms 48556 KB Output is correct
14 Correct 133 ms 36012 KB Output is correct
15 Correct 161 ms 48804 KB Output is correct
16 Correct 180 ms 45944 KB Output is correct
17 Correct 165 ms 52296 KB Output is correct
18 Correct 183 ms 50652 KB Output is correct
19 Incorrect 55 ms 16476 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 6236 KB Output is correct
2 Correct 3 ms 6236 KB Output is correct
3 Execution timed out 2078 ms 26396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6236 KB Output is correct
2 Correct 3 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 4 ms 6488 KB Output is correct
5 Correct 4 ms 6488 KB Output is correct
6 Correct 3 ms 6504 KB Output is correct
7 Correct 4 ms 6488 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Incorrect 3 ms 6232 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6232 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 6236 KB Output is correct
2 Correct 3 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 4 ms 6488 KB Output is correct
5 Correct 4 ms 6488 KB Output is correct
6 Correct 3 ms 6504 KB Output is correct
7 Correct 4 ms 6488 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 95 ms 36544 KB Output is correct
10 Correct 116 ms 45056 KB Output is correct
11 Correct 136 ms 43888 KB Output is correct
12 Correct 136 ms 46380 KB Output is correct
13 Correct 131 ms 48556 KB Output is correct
14 Correct 133 ms 36012 KB Output is correct
15 Correct 161 ms 48804 KB Output is correct
16 Correct 180 ms 45944 KB Output is correct
17 Correct 165 ms 52296 KB Output is correct
18 Correct 183 ms 50652 KB Output is correct
19 Execution timed out 2078 ms 26396 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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