oj.uz

Submission #429813

# Submission time Handle Problem Language Result Execution time Memory
429813 2021-06-16T09:47:52 Z Sundavar Swapping Cities (APIO20_swap) C++14
0 / 100
 328 ms 77656 KB 
#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;
    vector<int> poss = *new vector<int>(3, 2e9);
};
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+1, graph[with.xx].poss.push_back(with.yy);
    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, g);
    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(), g), 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;

    sort(graph[v].poss.begin(), graph[v].poss.end());
    graph[v].poss.resize(3);

    //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[a].father[i].xx == -1) continue;
        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 == -1 || graph[b].father[i].xx == -1 ) continue;
        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){
    graph.resize(N);
    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]});
    }
    cnt(0);
    build(0, {-1, 0}, 0, new segTree(), 0, 0);
}
int at(int v, int a, int b){
    if(graph[v].poss[0] != min(a,b)) return graph[v].poss[0];
    if(graph[v].poss[1] != max(a,b)) return graph[v].poss[1];
    return graph[v].poss[2];
}
pii get(int poz, int d){
    int mnm = 2e9;
    /*while(graph[poz].depth > d){
        if(graph[poz].poz == 0){
            int f = graph[poz].father[0].xx, y = graph[poz].father[0].yy;
            mnm = min(mnm, at(f, y, 2e9));
            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 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(a.yy, l.yy) > 1e9) ? -1 : max(a.yy, l.yy));
    pii b = get(X, graph[l.xx].depth+1);
    int mnm = min(a.yy, b.yy);
    mnm = min(mnm, at(l.xx, graph[a.xx].father[0].yy, graph[b.xx].father[0].yy));
    return ( (max(mnm, l.yy) > 1e9) ? -1 : max(mnm, l.yy));
}

/*int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);
  
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}*/

Compilation message

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, g);
      |        ~~~~~~~~~~~~~~~~~~~^~~
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++)
      |                      ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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