oj.uz

답안 #541597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541597 2022-03-23T19:58:02 Z cadmiumsky Golf (JOI17_golf) C++14
100 / 100
 3792 ms 995360 KB 
#include <bits/stdc++.h>
//#define int long long
using namespace std;

namespace G { // nodul 0 este o santinela la care se pointeaza in mod inutil (i.e. cand stergi din AINT)
  deque<pair<int, 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, t;
    tie(x, t) = deq.front();
    deq.pop_front();
    if(t != time[x])
      return bdfs();
    //cerr << x << ' ' <<time[x] << '\n';
    if(x == u || x == v)
      return time[x];
    for(auto [y, pt] : g[x]) {
      if(time[y] > time[x] + pt || time[y] == -1) {
        time[y] = time[x] + pt;
        //cerr << "---> " << y << ' ' <<time[y] << '\n';
        if(pt == 0)  
          deq.push_front({y, time[y]});
        else
          deq.push_back({y, time[y]});
      }
    }
    return bdfs();
  }
  int start(int S, int T, int U, int V) {
    deq.push_back({S, 1});
    deq.push_back({T, 1});
    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;


signed 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:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     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:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [x1, y1, x2, y2] : squares) {
      |              ^
golf.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [tlin, aaa, bbb] : forb) {
      |              ^
golf.cpp:76: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]
   76 |       while(temp < forb.size() && abs(get<0>(forb[temp])) < tlin) {
      |             ~~~~~^~~~~~~~~~~~~
golf.cpp:89: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]
   89 |       while(ptr < forb.size() && abs(get<0>(forb[ptr])) < tlin) {
      |             ~~~~^~~~~~~~~~~~~
golf.cpp:109: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]
  109 |     while(temp < forb.size()) {
      |           ~~~~~^~~~~~~~~~~~~
golf.cpp:122: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]
  122 |     while(ptr < forb.size()) {
      |           ~~~~^~~~~~~~~~~~~
golf.cpp:142:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |     for(auto &[a1, b1, c1, d1] : squares)
      |               ^
golf.cpp:147: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]
  147 |     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:155:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |     for(auto [poz, l, r, gid] : hor) { // init map
      |              ^
golf.cpp:160:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  160 |     for(auto [poz, l, r, gid] : ver) {
      |              ^
golf.cpp:171:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  171 |     for(auto &[poz, l, r, gid] : hor) { // set to normalization
      |               ^
golf.cpp:176:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |     for(auto &[poz, l, r, gid] : ver) {
      |               ^
golf.cpp: In function 'void MKG::AINT::update(int, int, int, int, int)':
golf.cpp:194:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  194 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
golf.cpp: In function 'void MKG::AINT::linkto(int, int, int, int, int, int)':
golf.cpp:210:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  210 |       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:224:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  224 |     for(auto [poz, l, r, gid] : ver) {
      |              ^
golf.cpp:233:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  233 |     for(auto [line, poz, gid] : qs) {
      |              ^
golf.cpp:234: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]
  234 |       while(ptr < hor.size() && get<0>(hor[ptr]) < abs(line)) {
      |             ~~~~^~~~~~~~~~~~
golf.cpp:247: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]
  247 |     while(ptr < hor.size()) {
      |           ~~~~^~~~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:267:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  267 |   for(auto &[x1, y1, x2, y2] : squares)
      |             ^
golf.cpp:273:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  273 |   for(auto [poz, l, r, gid] : hor) {
      |            ^
golf.cpp:279:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  279 |   for(auto [poz, l, r, gid] : ver) {
      |            ^
golf.cpp:301:35: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
  301 |   cout << G::start(S, T, U, V) << '\n';
      |                                   ^~~~
golf.cpp:301:35: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:301:35: warning: 'V' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:301: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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 16 ms 5768 KB Output is correct
6 Correct 21 ms 5768 KB Output is correct
7 Correct 14 ms 5768 KB Output is correct
8 Correct 14 ms 5768 KB Output is correct
9 Correct 15 ms 5780 KB Output is correct
10 Correct 17 ms 5768 KB Output is correct
11 Correct 16 ms 5968 KB Output is correct
12 Correct 14 ms 5720 KB Output is correct
13 Correct 21 ms 5828 KB Output is correct
14 Correct 14 ms 5768 KB Output is correct
15 Correct 4 ms 1296 KB Output is correct
16 Correct 7 ms 3084 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 16 ms 5768 KB Output is correct
6 Correct 21 ms 5768 KB Output is correct
7 Correct 14 ms 5768 KB Output is correct
8 Correct 14 ms 5768 KB Output is correct
9 Correct 15 ms 5780 KB Output is correct
10 Correct 17 ms 5768 KB Output is correct
11 Correct 16 ms 5968 KB Output is correct
12 Correct 14 ms 5720 KB Output is correct
13 Correct 21 ms 5828 KB Output is correct
14 Correct 14 ms 5768 KB Output is correct
15 Correct 4 ms 1296 KB Output is correct
16 Correct 7 ms 3084 KB Output is correct
17 Correct 25 ms 6244 KB Output is correct
18 Correct 21 ms 6148 KB Output is correct
19 Correct 21 ms 6276 KB Output is correct
20 Correct 19 ms 6256 KB Output is correct
21 Correct 19 ms 6404 KB Output is correct
22 Correct 19 ms 6404 KB Output is correct
23 Correct 20 ms 6264 KB Output is correct
24 Correct 20 ms 6276 KB Output is correct
25 Correct 18 ms 6344 KB Output is correct
26 Correct 19 ms 6304 KB Output is correct
27 Correct 4 ms 1680 KB Output is correct
28 Correct 8 ms 3084 KB Output is correct
29 Correct 9 ms 3084 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 16 ms 5768 KB Output is correct
6 Correct 21 ms 5768 KB Output is correct
7 Correct 14 ms 5768 KB Output is correct
8 Correct 14 ms 5768 KB Output is correct
9 Correct 15 ms 5780 KB Output is correct
10 Correct 17 ms 5768 KB Output is correct
11 Correct 16 ms 5968 KB Output is correct
12 Correct 14 ms 5720 KB Output is correct
13 Correct 21 ms 5828 KB Output is correct
14 Correct 14 ms 5768 KB Output is correct
15 Correct 4 ms 1296 KB Output is correct
16 Correct 7 ms 3084 KB Output is correct
17 Correct 25 ms 6244 KB Output is correct
18 Correct 21 ms 6148 KB Output is correct
19 Correct 21 ms 6276 KB Output is correct
20 Correct 19 ms 6256 KB Output is correct
21 Correct 19 ms 6404 KB Output is correct
22 Correct 19 ms 6404 KB Output is correct
23 Correct 20 ms 6264 KB Output is correct
24 Correct 20 ms 6276 KB Output is correct
25 Correct 18 ms 6344 KB Output is correct
26 Correct 19 ms 6304 KB Output is correct
27 Correct 4 ms 1680 KB Output is correct
28 Correct 8 ms 3084 KB Output is correct
29 Correct 9 ms 3084 KB Output is correct
30 Correct 3147 ms 919540 KB Output is correct
31 Correct 3154 ms 919456 KB Output is correct
32 Correct 3541 ms 929936 KB Output is correct
33 Correct 3656 ms 929188 KB Output is correct
34 Correct 3090 ms 939332 KB Output is correct
35 Correct 3792 ms 939388 KB Output is correct
36 Correct 3084 ms 939272 KB Output is correct
37 Correct 3392 ms 939444 KB Output is correct
38 Correct 3280 ms 939428 KB Output is correct
39 Correct 3477 ms 939756 KB Output is correct
40 Correct 2201 ms 974368 KB Output is correct
41 Correct 2196 ms 974224 KB Output is correct
42 Correct 2302 ms 984928 KB Output is correct
43 Correct 2171 ms 960068 KB Output is correct
44 Correct 2257 ms 970312 KB Output is correct
45 Correct 2223 ms 970292 KB Output is correct
46 Correct 2175 ms 970484 KB Output is correct
47 Correct 2236 ms 970384 KB Output is correct
48 Correct 2206 ms 995360 KB Output is correct
49 Correct 2224 ms 995304 KB Output is correct
50 Correct 9 ms 3076 KB Output is correct
51 Correct 9 ms 3132 KB Output is correct
52 Correct 10 ms 3084 KB Output is correct