oj.uz

답안 #541587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541587 2022-03-23T19:35:07 Z cadmiumsky Golf (JOI17_golf) C++14
10 / 100
 22 ms 6268 KB 
#include <bits/stdc++.h>

using namespace std;

namespace G { // nodul 0 este o santinela la care se pointeaza in mod inutil (i.e. cand stergi din AINT)
  deque<int> deq;
  vector<int> time;
  vector<vector<pair<int, int> > > g;
  int push() { g.push_back(vector<pair<int, int> >()); return g.size() - 1; }
  void push(int u, int v, int w) { // w ar trebui sa fie doar 1 sau 0
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  void pushdir(int u, int v, int w) { g[u].push_back({v, w}); } 
  int u, v;
  int bdfs() {
    if(deq.size() == 0)
      return -1;
    int x;
    x = deq.front();
    deq.pop_front();
    //cerr << x << ' ' <<time[x] << '\n';
    if(x == u || x == v)
      return time[x];
    for(auto [y, pt] : g[x]) {
      if(time[y] == -1) {
        time[y] = time[x] + pt;
        //cerr << "---> " << y << ' ' <<time[y] << '\n';
        if(pt == 0)  
          deq.push_front(y);
        else
          deq.push_back(y);
      }
    }
    return bdfs();
  }
  int start(int S, int T, int U, int V) {
    deq.push_back(S);
    deq.push_back(T);
    tie(u, v) = {U, V};
    time.resize(g.size(), -1);
    time[S] = 1;
    time[T] = 1;
    return bdfs();
  }
}

// x1, y1, x2, y2
vector<tuple<int,int,int,int> > squares;

namespace Norm {
  multiset<int> app;
  vector<tuple<int,int,int> > forb;
  void make(vector<tuple<int,int,int,int> > &hor, int s, int t, int u, int v) {
    for(auto [x1, y1, x2, y2] : squares) {
      forb.emplace_back(x1, y1, y2);
      forb.emplace_back(-x2, y1, y2);
    }
    forb.push_back({s, t, t});
    forb.push_back({-s, t, t});
    forb.push_back({-u, v, v});
    forb.push_back({u, v, v});
    sort(forb.begin(), forb.end(), [&](auto tp1,  auto tp2) {
      return abs(get<0>(tp1)) < abs(get<0>(tp2)) || 
            (abs(get<0>(tp1)) == abs(get<0>(tp2)) && get<0>(tp1) > get<0>(tp2));
    });
    app.insert(0);
    app.insert(1e9 + 1);
    int ptr = 0, a, b, c, lin, col1, col2;
    int temp;
    for(auto [tlin, aaa, bbb] : forb) {
      tlin = abs(tlin);
      temp = ptr;
      while(temp < forb.size() && abs(get<0>(forb[temp])) < tlin) {
        tie(lin, col1, col2) = forb[temp];
        if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
          temp++;
          continue;
        }
        if(lin < 0) {
          app.erase(col1);
          app.erase(col2);
        }
        temp++;
      }
      temp = ptr;
      while(ptr < forb.size() && abs(get<0>(forb[ptr])) < tlin) {
        tie(a, b, c) = forb[ptr];
        auto it = app.upper_bound(b);
        hor.push_back({abs(a), *prev(it), *it, G::push()});
        ptr++;
      }
      while(temp < ptr) {
        tie(lin, col1, col2) = forb[temp];
        if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
          temp++;
          continue;
        }
        if(lin > 0) {
          app.insert(col1);
          app.insert(col2);
        }
        temp++;
      }
    }
    temp = ptr;
    while(temp < forb.size()) {
      tie(lin, col1, col2) = forb[temp];
      if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
        temp++;
        continue;
      }
      if(lin < 0) {
        app.erase(col1);
        app.erase(col2);
      }
      temp++;
    }
    temp = ptr;
    while(ptr < forb.size()) {
      tie(a, b, c) = forb[ptr];
      auto it = app.upper_bound(b);
      hor.push_back({abs(a), *prev(it), *it, G::push()});
      ptr++;
    }
    while(temp < ptr) {
      tie(lin, col1, col2) = forb[temp];
      if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
        temp++;
        continue;
      }
      if(lin > 0) {
        app.insert(col1);
        app.insert(col2);
      }
      temp++;
    }
    forb.clear();
    app.clear();
    for(auto &[a1, b1, c1, d1] : squares)
      swap(a1, b1), swap(c1, d1);
    sort(hor.begin(), hor.end());
    vector<tuple<int,int,int,int> > thor;
    thor.push_back(hor[0]);
    for(int i = 1; i < hor.size(); i++) {
      if(get<0>(hor[i]) != get<0>(hor[i - 1]) || get<1>(hor[i]) != get<1>(hor[i - 1]) || get<2>(hor[i]) != get<2>(hor[i - 1]))
        thor.push_back(hor[i]);
    }
    hor = move(thor);
  }
  map<int,int> mp[2];
  int normalize(vector<tuple<int,int,int,int>>& hor, vector<tuple<int,int,int,int>>& ver) {
    for(auto [poz, l, r, gid] : hor) { // init map
      mp[1][l];
      mp[1][r];
      mp[0][poz];
    }
    for(auto [poz, l, r, gid] : ver) {
      mp[0][l];
      mp[0][r];
      mp[1][poz];
    }
    int cnt = 1;
    for(auto &x : mp[0])
      x.second = cnt++;
    cnt = 1;
    for(auto &x : mp[1])
      x.second = cnt++;
    for(auto &[poz, l, r, gid] : hor) { // set to normalization
      poz = mp[0][poz];
      l = mp[1][l];
      r = mp[1][r];
    }
    for(auto &[poz, l, r, gid] : ver) {
      poz = mp[1][poz];
      l = mp[0][l];
      r = mp[0][r];
    }
    return max(mp[0].size(), mp[1].size());
  }
}

namespace MKG {
  namespace AINT {
    vector<int> aint;
    int n;
    void update(int poz, int gid, int node = 1, int cl = 1, int cr = n) {
      if(cl == cr) {
        aint[node] = gid;
        return;
      }
      int mid = cl + cr >> 1;
      if(poz <= mid)
        update(poz, gid, 2 * node, cl, mid);
      else
        update(poz, gid, 2 * node + 1, mid + 1, cr);
      aint[node] = G::push();
      G::pushdir(aint[node], aint[2 * node], 0);
      G::pushdir(aint[node], aint[2 * node + 1], 0);
    }
    void linkto(int gid, int l, int r, int node = 1, int cl = 1, int cr = n) {
      if(r < cl || cr < l)
        return;
      if(l <= cl && cr <= r) {
        G::pushdir(gid, aint[node], 1);
        return;
      }
      int mid = cl + cr >> 1;
      linkto(gid, l, r, 2 * node, cl, mid);
      linkto(gid, l, r, 2 * node + 1, mid + 1, cr);
    }
    void reset(int nlen) {
      n = nlen + 1;
      aint.resize(n * 4);
    }
  }
  void start(vector<tuple<int,int,int,int> > ver, vector<tuple<int,int,int,int> > hor, int ASIZE) {
    AINT::reset(ASIZE);
    //  1  1  1 -- add
    // -1  1  1 -- erase
    vector<tuple<int,int,int> > qs;
    for(auto [poz, l, r, gid] : ver) {
      qs.push_back({l, poz, gid});
      qs.push_back({-r - 1, poz, gid});
    }
    sort(qs.begin(), qs.end(), [&](auto tp1,  auto tp2) {
      return abs(get<0>(tp1)) < abs(get<0>(tp2)) || 
            (abs(get<0>(tp1)) == abs(get<0>(tp2)) && get<0>(tp1) < get<0>(tp2));
    });
    int ptr = 0, a, l, r, tempid;
    for(auto [line, poz, gid] : qs) {
      while(ptr < hor.size() && get<0>(hor[ptr]) < abs(line)) {
        tie(a, l, r, tempid) = hor[ptr];
        //cerr << tempid << ' '<< l << ' ' << r << '\n';
        AINT::linkto(tempid, l, r);
        ptr++;
      }
      if(line < 0)
        //cerr << "- " << poz << ' '<< gid << '\n', 
        AINT::update(poz, 0);
      else
        //cerr << "+ " << poz << ' '<< gid << '\n', 
        AINT::update(poz, gid);
    }
    while(ptr < hor.size()) {
      tie(a, l, r, tempid) = hor[ptr];
      AINT::linkto(tempid, l, r);
      //cerr << tempid << ' '<< l << ' ' << r << '\n';
      ptr++;
    }
    //cerr << '\n';
    return;
  }
}

// poz, [l, r], graphID
vector<tuple<int,int,int,int> > hor, ver;


int main() {
  int n;
  int s, t, u, v;
  cin >> s >> t >> u >> v >> n;
  squares.resize(n);
  for(auto &[x1, y1, x2, y2] : squares)  
    cin >> x1 >> x2 >> y1 >> y2;
  G::push();
  Norm::make(hor, s, t, u, v);
  Norm::make(ver, t, s, v, u);
  int S, T, U, V;
  for(auto [poz, l, r, gid] : hor) {
    if(poz == s && l <= t && t <= r)
      T = gid;
    if(poz == u && l <= v && v <= r)
      V = gid;
  }
  for(auto [poz, l, r, gid] : ver) {
    if(poz == t && l <= s && s <= r)
      S = gid;
    if(poz == v && l <= u && u <= r)
      U = gid;
  }
  //cerr << "Horisontal:\n";
  //for(auto [line, l, r, gid] : hor)
    //cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
  //cerr << "Vertical:\n";
  //for(auto [line, l, r, gid] : ver)
    //cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
  int ASIZE = Norm::normalize(hor, ver);
  //cerr << "Horisontal:\n";
  //for(auto [line, l, r, gid] : hor)
    //cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
  //cerr << "Vertical:\n";
  //for(auto [line, l, r, gid] : ver)
    //cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
  //cerr << "</>" << S << ' ' << T << ' ' << U << ' ' << V << '\n';
  MKG::start(ver, hor, ASIZE);
  MKG::start(hor, ver, ASIZE);
  cout << G::start(S, T, U, V) << '\n';
}

Compilation message

golf.cpp: In function 'int G::bdfs()':
golf.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [y, pt] : g[x]) {
      |              ^
golf.cpp: In function 'void Norm::make(std::vector<std::tuple<int, int, int, int> >&, int, int, int, int)':
golf.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [x1, y1, x2, y2] : squares) {
      |              ^
golf.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for(auto [tlin, aaa, bbb] : forb) {
      |              ^
golf.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       while(temp < forb.size() && abs(get<0>(forb[temp])) < tlin) {
      |             ~~~~~^~~~~~~~~~~~~
golf.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       while(ptr < forb.size() && abs(get<0>(forb[ptr])) < tlin) {
      |             ~~~~^~~~~~~~~~~~~
golf.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     while(temp < forb.size()) {
      |           ~~~~~^~~~~~~~~~~~~
golf.cpp:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     while(ptr < forb.size()) {
      |           ~~~~^~~~~~~~~~~~~
golf.cpp:140:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |     for(auto &[a1, b1, c1, d1] : squares)
      |               ^
golf.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i = 1; i < hor.size(); i++) {
      |                    ~~^~~~~~~~~~~~
golf.cpp: In function 'int Norm::normalize(std::vector<std::tuple<int, int, int, int> >&, std::vector<std::tuple<int, int, int, int> >&)':
golf.cpp:153:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |     for(auto [poz, l, r, gid] : hor) { // init map
      |              ^
golf.cpp:158:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |     for(auto [poz, l, r, gid] : ver) {
      |              ^
golf.cpp:169:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  169 |     for(auto &[poz, l, r, gid] : hor) { // set to normalization
      |               ^
golf.cpp:174:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  174 |     for(auto &[poz, l, r, gid] : ver) {
      |               ^
golf.cpp: In function 'void MKG::AINT::update(int, int, int, int, int)':
golf.cpp:192:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  192 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
golf.cpp: In function 'void MKG::AINT::linkto(int, int, int, int, int, int)':
golf.cpp:208:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  208 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
golf.cpp: In function 'void MKG::start(std::vector<std::tuple<int, int, int, int> >, std::vector<std::tuple<int, int, int, int> >, int)':
golf.cpp:222:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  222 |     for(auto [poz, l, r, gid] : ver) {
      |              ^
golf.cpp:231:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  231 |     for(auto [line, poz, gid] : qs) {
      |              ^
golf.cpp:232:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |       while(ptr < hor.size() && get<0>(hor[ptr]) < abs(line)) {
      |             ~~~~^~~~~~~~~~~~
golf.cpp:245:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |     while(ptr < hor.size()) {
      |           ~~~~^~~~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:265:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  265 |   for(auto &[x1, y1, x2, y2] : squares)
      |             ^
golf.cpp:271:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  271 |   for(auto [poz, l, r, gid] : hor) {
      |            ^
golf.cpp:277:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  277 |   for(auto [poz, l, r, gid] : ver) {
      |            ^
golf.cpp:299:35: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
  299 |   cout << G::start(S, T, U, V) << '\n';
      |                                   ^~~~
golf.cpp:299:35: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:299:35: warning: 'V' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:299:35: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 15 ms 5760 KB Output is correct
6 Correct 19 ms 5792 KB Output is correct
7 Correct 14 ms 5768 KB Output is correct
8 Correct 15 ms 5776 KB Output is correct
9 Correct 14 ms 5768 KB Output is correct
10 Correct 17 ms 5768 KB Output is correct
11 Correct 16 ms 5740 KB Output is correct
12 Correct 16 ms 5768 KB Output is correct
13 Correct 17 ms 5740 KB Output is correct
14 Correct 15 ms 5848 KB Output is correct
15 Correct 3 ms 1264 KB Output is correct
16 Correct 8 ms 3084 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 15 ms 5760 KB Output is correct
6 Correct 19 ms 5792 KB Output is correct
7 Correct 14 ms 5768 KB Output is correct
8 Correct 15 ms 5776 KB Output is correct
9 Correct 14 ms 5768 KB Output is correct
10 Correct 17 ms 5768 KB Output is correct
11 Correct 16 ms 5740 KB Output is correct
12 Correct 16 ms 5768 KB Output is correct
13 Correct 17 ms 5740 KB Output is correct
14 Correct 15 ms 5848 KB Output is correct
15 Correct 3 ms 1264 KB Output is correct
16 Correct 8 ms 3084 KB Output is correct
17 Correct 21 ms 6192 KB Output is correct
18 Correct 21 ms 6248 KB Output is correct
19 Incorrect 22 ms 6268 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 15 ms 5760 KB Output is correct
6 Correct 19 ms 5792 KB Output is correct
7 Correct 14 ms 5768 KB Output is correct
8 Correct 15 ms 5776 KB Output is correct
9 Correct 14 ms 5768 KB Output is correct
10 Correct 17 ms 5768 KB Output is correct
11 Correct 16 ms 5740 KB Output is correct
12 Correct 16 ms 5768 KB Output is correct
13 Correct 17 ms 5740 KB Output is correct
14 Correct 15 ms 5848 KB Output is correct
15 Correct 3 ms 1264 KB Output is correct
16 Correct 8 ms 3084 KB Output is correct
17 Correct 21 ms 6192 KB Output is correct
18 Correct 21 ms 6248 KB Output is correct
19 Incorrect 22 ms 6268 KB Output isn't correct
20 Halted 0 ms 0 KB -