oj.uz

답안 #1056756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1056756 2024-08-13T10:52:20 Z vjudge1 자매 도시 (APIO20_swap) C++17
0 / 100
 663 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[bot]);
    int b = query(roots[m],1,nn,tin[X]);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9744 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 3 ms 9820 KB Output is correct
6 Correct 2 ms 10032 KB Output is correct
7 Correct 3 ms 9992 KB Output is correct
8 Correct 3 ms 10072 KB Output is correct
9 Correct 60 ms 34696 KB Output is correct
10 Correct 74 ms 41824 KB Output is correct
11 Correct 68 ms 41028 KB Output is correct
12 Correct 73 ms 42560 KB Output is correct
13 Correct 76 ms 43276 KB Output is correct
14 Correct 78 ms 34880 KB Output is correct
15 Correct 309 ms 45636 KB Output is correct
16 Correct 309 ms 44356 KB Output is correct
17 Correct 337 ms 47168 KB Output is correct
18 Correct 394 ms 46596 KB Output is correct
19 Runtime error 663 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9744 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Incorrect 215 ms 43148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9744 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 3 ms 9820 KB Output is correct
6 Correct 2 ms 10032 KB Output is correct
7 Correct 3 ms 9992 KB Output is correct
8 Correct 3 ms 10072 KB Output is correct
9 Runtime error 266 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 266 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9744 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 3 ms 9820 KB Output is correct
6 Correct 2 ms 10032 KB Output is correct
7 Correct 3 ms 9992 KB Output is correct
8 Correct 3 ms 10072 KB Output is correct
9 Correct 60 ms 34696 KB Output is correct
10 Correct 74 ms 41824 KB Output is correct
11 Correct 68 ms 41028 KB Output is correct
12 Correct 73 ms 42560 KB Output is correct
13 Correct 76 ms 43276 KB Output is correct
14 Correct 78 ms 34880 KB Output is correct
15 Correct 309 ms 45636 KB Output is correct
16 Correct 309 ms 44356 KB Output is correct
17 Correct 337 ms 47168 KB Output is correct
18 Correct 394 ms 46596 KB Output is correct
19 Incorrect 215 ms 43148 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 266 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -