oj.uz

답안 #545962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545962 2022-04-05T17:39:44 Z cadmiumsky Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 151600 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#warning W e PREFIXUL
using namespace std;
 
// Pentru fiecare bucata de radical, avem in total N^2/B muchii incluse direct (idfk)
// Muchii care ating partial (se includ sau pe prefix suffix etc) pot fi doar O(B)
// pentru fiecare query, procesam muchiile de primul tip (compl e spusa), iar dupa punem fortat (si dupa scoatem)
// toate muchiile de al doilea tip. Astfel, la fiecare query avem compl O(Q * B).
// Wow, chiar a fost greu sa scrie si ei un editorial atat de uman (nu ca as fi eu zeu, dar mna)
 
int B;
const int nmax = 1e5 + 5, qmax = 1e5 + 5, cmax = 1e5 + 5;
using pii = pair<int,int>;
int n, q, c;
 
// decomp dupa POZITIE
namespace Driver {
  namespace DSU {
    int area[nmax], dsu[nmax];
    vector<pair<int,int> > bk;
    int cc;
    void init(int n) {
      for(int i = 0; i < n; i++)
        dsu[i] = i, area[i] = 1;
      bk.clear();
      cc = n;
      return;
    }
    int father(int x) {
      return (dsu[x] == x? x : father(dsu[x]));
    }
    int gettime() {return bk.size();}
    void unite(int a, int b) {
      a = father(a);
      b = father(b);
      if(a == b) 
        return;
      if(area[a] > area[b])
        swap(a, b);
      dsu[b] = a;
      area[a] += area[b];
      dsu[b] = a;
      bk.push_back({b, a});
      cc--;
    }
    int rollback() {
      if(bk.size() == 0)
        return -1;
      int a, b;
      tie(b, a) = bk.back();
      dsu[b] = b;
      area[a] -= area[b];
      cc++;
      bk.pop_back();
      return bk.size();
    }
    int query() { return cc; }
  }
  
  unordered_map<int, unordered_map<int,int> > atredge;
  unordered_map<int, unordered_map<int,int> > open;
  vector< pair<int,int> > edge;
  vector< vector< pair<int,int> > > span;
  vector< pair<int, int> > qs;
  vector<int> rez;
  struct Bucket {
    vector<int> included;
    vector<tuple<int,int,int> > partial;
    int L, R;
    vector<int> queries;
    Bucket(int l, int r) {tie(L, R) = {l, r};}
    void apply() {
      while(DSU::rollback() > 0);
      sort(queries.begin(), queries.end(), [&](auto x, auto y) {return qs[x].second < qs[y].second;});
      sort(included.begin(), included.end(), [&](auto x, auto y) {return edge[x].second < edge[y].second;});
      int ptr = 0;
      for(auto idx : queries) {
        int poz, time;
        tie(poz, time) = qs[idx];
        while(ptr < included.size() && edge[included[ptr]].second <= time)
          DSU::unite(edge[included[ptr]].first, edge[included[ptr]].second), ptr++;
        int temporary = DSU::gettime();
        for(auto X : partial) {
          int edg, l, r;
          tie(edg, l, r) = X;
          if(l <= poz && poz <= r && edge[edg].second <= time)
            DSU::unite(edge[edg].first, edge[edg].second);
        }
        rez[idx] += DSU::query() - (n - qs[idx].second - 1);
        if(DSU::gettime() > temporary)
          while(DSU::rollback() > temporary);
      }
    }
  };
  vector<Bucket> decomp;
  namespace Init {
    void prepare() {
      int l = 0, r = min(c - 1, B - 1);
      while(l < c) {
        decomp.push_back(Bucket(l, r));
        l += B;
        r = min(c - 1, r + B);
      }
      decomp.push_back(Bucket(2 * c + 1, 2 *  c + 2));
      for(int i = 0; i < edge.size(); i++) {
        int ptr = 0;
        for(auto X : span[i]) {
          tie(l, r) = X;
          while(decomp[ptr].R < l)
            ptr++;
          if(ptr == decomp.size())
            break;
          decomp[ptr].partial.push_back({i, l, r});
          if(r <= decomp[ptr].R)
            continue;
          ptr++;
          while(l <= decomp[ptr].L && decomp[ptr].R <= r)
            decomp[ptr++].included.push_back(i);
          if(!(decomp[ptr].R < l || decomp[ptr].L > r))
            decomp[ptr].partial.push_back({i, l, r});
        }
      }
      for(int i = 0; i < q; i++)
        decomp[qs[i].first / B].queries.push_back(i);
      return;
    }
    void read(vector<int> t, vector<int>& lf, vector<int>& rh, vector<int> w, vector<int> p) {
      rez.resize(q, 0);
      for(int i = 0, ptr; i < c; i++) {
        int x, y;
        tie(x, y) = {lf[i], rh[i]};
        if(x > y)
          swap(lf[i], rh[i]), swap(x, y);
        if(atredge.find(x) == atredge.end()  || atredge[x].find(y) == atredge[x].end())
          atredge[x][y] = edge.size(), span.push_back(vector<pii>()), edge.push_back({x, y});
        ptr = atredge[x][y];
        open[x][y];
        if(open[x][y] == 0)
          span[ptr].push_back({i, -1});
        open[x][y] += -2 * t[i] + 1;
        if(open[x][y] == 0)
          span[ptr].back().second = i - 1;
      }
      int x, y, val;
      for(auto X : open) {
        x = X.first;
        for(auto Y : X.second) {
          tie(y, val) = Y;
          if(val > 0)
            span[atredge[x][y]].back().second = c - 1;
        }
      }
      for(int i = 0; i < q; i++)
        qs.push_back({w[i], p[i]});
      return;
    }
  }
  namespace Decomp {
    void start() {
      for(auto& x : decomp)
        x.apply();
    }
  }
  void erase() {
    DSU::init(n);
    decomp.clear();
    span.clear();
    qs.clear();
    edge.clear();
    atredge.clear();
    open.clear();
  }
}
 
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
  n = N;
  c = T.size();
  q = W.size();
  B = 200;
  Driver::DSU::init(n);
  Driver::Init::read(T, X, Y, W, P);
  Driver::Init::prepare();
  Driver::Decomp::start();
  Driver::erase();
  for(int i = 0; i < c; i++) {
    X[i] = N - X[i] - 1; 
    Y[i] = N - Y[i] - 1; 
  }
  for(int i = 0; i < q; i++)
    P[i] = N - P[i] - 2;
  Driver::Init::read(T, X, Y, W, P);
  Driver::Init::prepare();
  Driver::Decomp::start();
  return Driver::rez;
}

Compilation message

collapse.cpp:3:2: warning: #warning W e PREFIXUL [-Wcpp]
    3 | #warning W e PREFIXUL
      |  ^~~~~~~
collapse.cpp: In member function 'void Driver::Bucket::apply()':
collapse.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while(ptr < included.size() && edge[included[ptr]].second <= time)
      |               ~~~~^~~~~~~~~~~~~~~~~
collapse.cpp: In function 'void Driver::Init::prepare()':
collapse.cpp:106: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]
  106 |       for(int i = 0; i < edge.size(); i++) {
      |                      ~~^~~~~~~~~~~~~
collapse.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Driver::Bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |           if(ptr == decomp.size())
      |              ~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 576 KB Output is correct
5 Correct 11 ms 812 KB Output is correct
6 Correct 86 ms 1876 KB Output is correct
7 Correct 3 ms 580 KB Output is correct
8 Correct 4 ms 636 KB Output is correct
9 Correct 11 ms 1876 KB Output is correct
10 Correct 92 ms 1940 KB Output is correct
11 Correct 137 ms 3040 KB Output is correct
12 Correct 947 ms 2900 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4564 KB Output is correct
2 Correct 40 ms 4540 KB Output is correct
3 Correct 171 ms 9016 KB Output is correct
4 Correct 54 ms 4684 KB Output is correct
5 Correct 322 ms 10296 KB Output is correct
6 Correct 723 ms 6064 KB Output is correct
7 Execution timed out 15050 ms 151600 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4544 KB Output is correct
2 Correct 40 ms 4512 KB Output is correct
3 Correct 50 ms 4664 KB Output is correct
4 Correct 58 ms 4700 KB Output is correct
5 Correct 618 ms 5200 KB Output is correct
6 Correct 1196 ms 6208 KB Output is correct
7 Execution timed out 15019 ms 86884 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 576 KB Output is correct
5 Correct 11 ms 812 KB Output is correct
6 Correct 86 ms 1876 KB Output is correct
7 Correct 3 ms 580 KB Output is correct
8 Correct 4 ms 636 KB Output is correct
9 Correct 11 ms 1876 KB Output is correct
10 Correct 92 ms 1940 KB Output is correct
11 Correct 137 ms 3040 KB Output is correct
12 Correct 947 ms 2900 KB Output is correct
13 Correct 35 ms 4564 KB Output is correct
14 Correct 40 ms 4540 KB Output is correct
15 Correct 171 ms 9016 KB Output is correct
16 Correct 54 ms 4684 KB Output is correct
17 Correct 322 ms 10296 KB Output is correct
18 Correct 723 ms 6064 KB Output is correct
19 Execution timed out 15050 ms 151600 KB Time limit exceeded
20 Halted 0 ms 0 KB -