oj.uz

Submission #1056784

# Submission time Handle Problem Language Result Execution time Memory
1056784 2024-08-13T11:10:25 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 674 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[bot]<=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 9564 KB Output is correct
3 Correct 2 ms 9564 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 10016 KB Output is correct
9 Correct 65 ms 33184 KB Output is correct
10 Correct 69 ms 39764 KB Output is correct
11 Correct 66 ms 39016 KB Output is correct
12 Correct 71 ms 40512 KB Output is correct
13 Correct 71 ms 41204 KB Output is correct
14 Correct 78 ms 33088 KB Output is correct
15 Correct 323 ms 41284 KB Output is correct
16 Correct 323 ms 40004 KB Output is correct
17 Correct 342 ms 42816 KB Output is correct
18 Correct 380 ms 42200 KB Output is correct
19 Runtime error 674 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 9564 KB Output is correct
3 Incorrect 228 ms 39308 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 9564 KB Output is correct
3 Correct 2 ms 9564 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 10016 KB Output is correct
9 Runtime error 274 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 274 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 9564 KB Output is correct
3 Correct 2 ms 9564 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 10016 KB Output is correct
9 Correct 65 ms 33184 KB Output is correct
10 Correct 69 ms 39764 KB Output is correct
11 Correct 66 ms 39016 KB Output is correct
12 Correct 71 ms 40512 KB Output is correct
13 Correct 71 ms 41204 KB Output is correct
14 Correct 78 ms 33088 KB Output is correct
15 Correct 323 ms 41284 KB Output is correct
16 Correct 323 ms 40004 KB Output is correct
17 Correct 342 ms 42816 KB Output is correct
18 Correct 380 ms 42200 KB Output is correct
19 Incorrect 228 ms 39308 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 274 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -