Submission #429730

#	Time	Username	Problem	Language	Result	Execution time	Memory
429730		Sundavar	Swapping Cities (APIO20_swap)	C++14	0 / 100	1 ms	384 KiB

swap

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef vector<int> vi;
struct segTree{
    vector<int> t, at;
    int maxN, id;
    segTree(){
        id = rng();
    }
    void init(int n){
        maxN = n, t.resize(2*n, 0);
        at.resize(n);
    }
    void update(int poz, int val){
        for(t[poz += maxN] = val; poz > 1; poz>>=1)
            t[poz>>1] = min(t[poz], t[poz^1]);
    }
    int get(int l, int r){
        int ans = 0;
        for(l += maxN, r += maxN; l < r; l>>=1, r>>=1){
            if(l&1) ans = min(ans, t[l++]);
            if(r&1) ans = min(ans, t[--r]);
        }
        return ans;
    }
};
typedef pair<int,int> pii;
#define xx first
#define yy second
struct node{
    vector<pii> to, tt, father = *new vector<pii>(20, {-1, 1e9});
    segTree* tree;
    int poz, cnt, depth = 0, g;
    bool was = false;
    multiset<int> here;
};
vector<node> graph;
int cnt(int v){
    graph[v].cnt = 1, graph[v].was = true;
    for(pii& a : graph[v].to)
        if(!graph[a.xx].was) graph[v].cnt += cnt(a.xx);
    graph[v].was = false;
    return graph[v].cnt;
}
bool sortFunc(pii a, pii b){
    return graph[a.xx].cnt < graph[b.xx].cnt;
}
void build(int v, pii with, int poz, segTree* tree, int g = 0, int s = 1){
    graph[v].g = g;
    //heavy-light
    if(with.xx != -1) graph[v].depth = graph[with.xx].depth;
    sort(graph[v].to.begin(), graph[v].to.end(), sortFunc);
    if(graph[v].to.size() > s) build(graph[v].to[s].xx, {v, graph[v].to[s].yy}, poz+1, tree);
    int mnm = 1e9;
    for(int i = s+1; i < graph[v].to.size(); i++)
        build(graph[v].to[i].xx, {v, graph[v].to[i].yy}, 0, new segTree()), mnm = min(mnm, graph[v].to[i].yy);
    if(graph[v].to.size() == 1) tree->init(poz+1);
    tree->update(poz, mnm);
    tree->at[graph[v].poz] = v;
    for(int i = s; i < graph[v].to.size(); i++)
        graph[v].here.insert(graph[v].to[i].yy);

    //lca
    graph[v].father[0] = with;
    int f = with.xx;
    for(int i = 1; i < 20 && f != -1; i++){
        graph[v].father[i] = {graph[f].father[i-1].xx, max(graph[f].father[i-1].yy, graph[v].father[i-1].yy)};
        f = graph[v].father[i].xx;
    }
}
pii lca(int a, int b){
    if(graph[a].depth < graph[b].depth);
    int mxm = 0;
    for(int i = 19; i >= 0; i--)
        if(graph[graph[a].father[i].xx].depth >= graph[b].depth)
            mxm = max(mxm, graph[a].father[i].yy), a = graph[a].father[i].xx;
    if(a == b) return {a, mxm};
    for(int i = 19; i >= 0; i--){
        if(graph[a].father[i].xx != graph[b].father[i].xx || i == 0){
            mxm = max(mxm, max(graph[a].father[i].yy, graph[b].father[i].yy));
            a = graph[a].father[i].xx, b = graph[b].father[i].xx;
        }
    }
    return {a,mxm};
    
}
void init(int N, int M, vi U, vi V, vi W){
    for(int i = 0; i < M; i++){
        graph[U[i]].to.push_back({V[i], W[i]});
        graph[V[i]].to.push_back({U[i], W[i]});
    }
    build(0, {-1, 0}, 0, new segTree(), 0, 0);
}
pii get(int poz, int d){
    int mnm = 1e9;
    while(graph[poz].depth > d){
        if(graph[poz].poz == 0){
            int f = graph[poz].father[0].xx, y = graph[poz].father[0].yy;
            graph[f].here.erase(graph[f].here.find(y));
            if(graph[f].here.size() > 0)
                mnm = min(mnm, *graph[f].here.begin());
            graph[f].here.insert(y);
            poz = f;
        }
        else{
            int to = max(0, graph[poz].poz - (graph[poz].depth - d) );
            mnm = min(mnm, graph[poz].tree->get(to, graph[poz].poz));
            poz = graph[poz].tree->at[to];
        }
    }
    return {poz, mnm};
}
int at(int f, int a, int b){
    int x = graph[a].father[0].yy, y = graph[b].father[0].yy;
    graph[f].here.erase(graph[f].here.find(y)), graph[f].here.erase(graph[f].here.find(x));
    int ans = 1e9;
    if(graph[f].here.size() > 0)
        ans = min(ans, *graph[f].here.begin());
    graph[f].here.insert(y), graph[f].here.insert(x); 
    return ans;
}
int getMinimumFuelCapacity(int X, int Y){
    pii l = lca(X,Y);
    if(graph[X].depth > graph[Y].depth) swap(X,Y);
    pii a = get(Y, graph[l.xx].depth+1);
    if(X == l.xx)
        return max(l.yy, a.yy);
    pii b = get(X, graph[l.xx].depth+1);
    int mnm = min(a.yy, b.yy);
    mnm = min(mnm, at(l.xx, a.xx, b.xx));
    return max(mnm, l.yy);
}

Compilation message (stderr)

swap.cpp: In function 'void build(int, pii, int, segTree*, int, int)':
swap.cpp:55:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if(graph[v].to.size() > s) build(graph[v].to[s].xx, {v, graph[v].to[s].yy}, poz+1, tree);
      |        ~~~~~~~~~~~~~~~~~~~^~~
swap.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = s+1; i < graph[v].to.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~~~~~~
swap.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = s; i < graph[v].to.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27