oj.uz

Submission #1056767

# Submission time Handle Problem Language Result Execution time Memory
1056767 2024-08-13T11:01:01 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 668 ms 524288 KB 
#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e9;
const int L = 2e5+1;

struct DSU {
  int n;
  vi dad,change,sz;
  DSU(){};
  DSU(int nn) {
    n = nn;
    dad.resize(n),change.assign(n,0),sz.assign(n,1);
    iota(dad.begin(),dad.end(),0ll);
  }

  int find(int x,int t) {
    if (!change[x] || change[x] > t) return x;
    return find(dad[x],t);
  }
  void unite(int x,int y,int t) {
    int a = find(x,t);
    int b = find(y,t);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a,b);
    dad[b] = a;
    sz[a]+=sz[b];
    change[b] = t;
  }
};

vi vv;

int idx(int xx) {
  return upper_bound(all(vv),xx)-vv.begin();
}

struct Node{
  int v;
  Node *l,*r;
  Node() {
    l = r = NULL;
    v = 0;
  }
  Node(int x) {
    v = x;
    l = r = NULL;
  }
  Node(Node* cp) {
    l = cp->l,r = cp->r,v = cp->v;
  }
  Node(Node* L,Node* R,int V = 0) {
    l = L;
    r = R;
    v = V;
  }
};

Node* build(int l,int r) {
  if (l == r) return new Node;
  int m = (l+r) >> 1;
  return new Node(build(l,m),build(m+1,r));
}

Node* update(Node* node,int l,int r,int L,int R,int v) {
  if (l >= L && r <= R) return new Node(node->l,node->r,node->v+v);
  int m = (l+r) >> 1;
  if (m >= L && m+1 <= R) return new Node(update(node->l,l,m,L,R,v),update(node->r,m+1,r,L,R,v),node->v);
  if (m >= L) return new Node(update(node->l,l,m,L,R,v),node->r,node->v);
  return new Node(node->l,update(node->r,m+1,r,L,R,v),node->v);
}

int query(Node* node,int l,int r,int p) {
  if (l == r) return node->v;
  int m = (l+r) >> 1;
  if (p<=m) return node->v+query(node->l,l,m,p);
  return node->v+query(node->r,m+1,r,p);
}


map<int,int> realy;
Node* roots[L];
vi change(L,inf),tin(L),tout(L),par(L),egdes[L];
int timer = 1;
DSU dsu;

int up[L][20];

void dfs(int node,int p) {
  par[node] = up[node][0] = p;
  tin[node] = timer++;
  for (auto it : egdes[node]) if (it != p) dfs(it,node);
  tout[node] = timer-1;
}
bool anc(int x,int y) {
  return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int a,int b) {
  if (anc(a,b)) return a;
  if (anc(b,a)) return b;
  for (int i=19;i>=0;i--) {
    if (!anc(up[a][i],b)) a = up[a][i];
  }
  return up[a][0];
}



int nn;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    nn = N;
    for (int i=0;i<M;i++) vv.push_back(W[i]);
    sort(all(vv));
    vv.erase(unique(all(vv)),vv.end());
    int cc = 1;
    for (auto it : vv) realy[cc++] = it; 
    for (int i=0;i<M;i++) {
      egdes[U[i]].push_back(V[i]);
      egdes[V[i]].push_back(U[i]);
    }
    dfs(0,0);
    for (int i=1;i<20;i++) {
      for (int j=0;j<N;j++) up[j][i] = up[up[j][i-1]][i-1];
    }
    if (M == N-1) {
      //tree case
      dsu = DSU(N);
      vector<pair<int,pii>> edges;
      for (int i=0;i<M;i++) edges.push_back({idx(W[i]),{U[i],V[i]}});
      sort(all(edges));
      for (auto it : edges) dsu.unite(it.ss.ff,it.ss.ss,it.ff);
      vi edg(N,0);
      int sz = vv.size();
      roots[0] = new Node;
      roots[0] = build(1,N);
      int ptr = 0;
      for (int i=1;i<=sz;i++) {
        roots[i] = roots[i-1];
        while (ptr < edges.size() && edges[ptr].ff == i) {
          edg[edges[ptr].ss.ff]++;
          edg[edges[ptr].ss.ss]++;
          if (edg[edges[ptr].ss.ff] == 3) {
            change[edges[ptr].ss.ff] = i;
            roots[i] = update(roots[i],1,N,tin[edges[ptr].ss.ff],tout[edges[ptr].ss.ff],1);
          }
          if (edg[edges[ptr].ss.ss] == 3) {
            change[edges[ptr].ss.ss] = i;
            roots[i] = update(roots[i],1,N,tin[edges[ptr].ss.ss],tout[edges[ptr].ss.ss],1);
          }
          ptr++;
        }
      }
      return;
    }
    assert(0);

}

int getMinimumFuelCapacity(int X, int Y) {
  int sz = vv.size();
  int l = 1;
  int r = sz;
  while (l<=r) {
    int m = (l+r) >> 1;
    if (dsu.find(X,m) != dsu.find(Y,m)) {
      l = m+1;
      continue;
    }
    if (!anc(X,Y) && !anc(Y,X)) {
      int a = query(roots[m],1,nn,tin[par[X]]);
      int b = query(roots[m],1,nn,tin[par[Y]]);
      int lc = lca(par[X],par[Y]);
      int c = query(roots[m],1,nn,tin[lc]);
      if (a+b-2*c+(change[lc]<=m)) r = m-1;
      else l = m+1;
      continue;
    }
    if (anc(Y,X)) swap(X,Y);
    if (X == par[Y]) {
      l = m+1;
      continue;
    }
    int bot = Y;
    for (int i=19;i>=0;i--) {
      if (!anc(up[bot][i],X)) bot = up[bot][i];
    }
    int a = query(roots[m],1,nn,tin[par[Y]]);
    int b = query(roots[m],1,nn,tin[bot]);
    if (a-b+(change[X]<=m)) r = m-1;
    else l = m+1;
  }
  if (l <= sz) return realy[l];
  return -1;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         while (ptr < edges.size() && edges[ptr].ff == i) {
      |                ~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 2 ms 9532 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 60 ms 33236 KB Output is correct
10 Correct 68 ms 39748 KB Output is correct
11 Correct 67 ms 39232 KB Output is correct
12 Correct 71 ms 40512 KB Output is correct
13 Correct 71 ms 41284 KB Output is correct
14 Correct 78 ms 32968 KB Output is correct
15 Correct 308 ms 41284 KB Output is correct
16 Correct 302 ms 40004 KB Output is correct
17 Correct 358 ms 42816 KB Output is correct
18 Correct 396 ms 42096 KB Output is correct
19 Runtime error 668 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 2 ms 9532 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Runtime error 281 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 281 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 2 ms 9532 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 60 ms 33236 KB Output is correct
10 Correct 68 ms 39748 KB Output is correct
11 Correct 67 ms 39232 KB Output is correct
12 Correct 71 ms 40512 KB Output is correct
13 Correct 71 ms 41284 KB Output is correct
14 Correct 78 ms 32968 KB Output is correct
15 Correct 308 ms 41284 KB Output is correct
16 Correct 302 ms 40004 KB Output is correct
17 Correct 358 ms 42816 KB Output is correct
18 Correct 396 ms 42096 KB Output is correct
19 Incorrect 216 ms 39244 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 281 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -