Submission #571113

#	Time	Username	Problem	Language	Result	Execution time	Memory
571113		cadmiumsky	Abduction 2 (JOI17_abduction2)	C++14	44 / 100	4660 ms	17124 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using ll = long long;

const int nmax = 2e5 + 5, inf = 1e9 + 5;

//#warning vectorii sa ii indexezi de la 1
int h[nmax], v[nmax]; int L, C;
int get(int a) { return  (a < 0? h[-a] : v[a]); }

namespace G {
  vector< vector<pii> > g;
  vector<ll> dp;
  
  void reset() {
    g.clear();
    dp.clear();
  }
  
  int newnode() {
    g.push_back(vector<pii>());
    dp.push_back(-1);
    return g.size() - 1;
  }
  
  void addedge(int x, int y, int c) { g[x].push_back({y, c}); }
  
  int startdfs(int node) {
    if(dp[node] != -1)
      return dp[node];
    for(auto [a, b] : g[node])
      dp[node] = max((ll)startdfs(a) + b, dp[node]);
    return dp[node];
  }
}

int start(int x, int y, bool hor, bool dir) {
  //cerr << hor << ' ' << dir << '\n';
  //auto cmp = [&](tii a, tii b) { return get(get<0>(a)) > get(get<0>(b)); };
  //priority_queue<tuple<int,int,int>, vector< tuple<int,int,int> >, decltype(cmp) > heap(cmp);
  auto cmp = [&](int a, int b) { return get(a) < get(b); };
  map<int, vector<pii>, decltype(cmp) > heap(cmp);
  G::reset();
  int source, sink = G::newnode(); // == 0
  int l[2] = {x, y}, r[2] = {x, y};
  if(hor)
    heap[-x].push_back({y, source = G::newnode()}),
    (dir == 0? l[1]-- : r[1]++);
  else
    heap[y].push_back({x, source = G::newnode()}),
    (dir == 0? l[0]-- : r[0]++);
  int node;
  while(!heap.empty()) {
    x = heap.begin()->first;
    //cerr << x << '\n';
    int dir = 0, target = get(x);
    if(x < 0)
      dir = 1;
    while(l[dir] > 0 && (dir == 0? h : v)[l[dir]] < target)
      l[dir]--;
    while(r[dir] <= (dir == 0? L : C) && (dir == 0? h : v)[r[dir]] < target)
      r[dir]++;
    //cerr << " > " << x << ' ' << get(x) << ' ' << l[dir] << ' ' << r[dir] << '\n';
    int lnode = sink, rnode = sink;
    if(l[dir] != 0)
      heap[(dir == 0? -1 : 1) * l[dir]].push_back({abs(x), lnode = G::newnode()});
    if(r[dir] <= (dir == 0? L : C))
      heap[(dir == 0? -1 : 1) * r[dir]].push_back({abs(x), rnode = G::newnode()});
  
    auto &vec = heap[x];
    for(auto [coord, atrnode] : vec) {
      G::addedge(atrnode, lnode, abs(coord - l[dir]));
      G::addedge(atrnode, rnode, abs(coord - r[dir]));
    }
    vec.clear();
    heap.erase(heap.begin());
  }
  //cerr << G::startdfs(source) << '\n';
//cerr << '\n';  
  return G::startdfs(source);
  
}

int main() {
  ios_base::sync_with_stdio(0);
  cin >> L >> C;
  int q;
  cin >> q;
  for(int i = 1; i <= L; i++)
    cin >> h[i];
  for(int i = 1; i <= C; i++)
    cin >> v[i];
  for(int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    cout << max({start(x, y, 1, 1), start(x, y, 0, 0)
              , start(x, y, 1, 0), start(x, y, 0, 1)}) << '\n';
    //cerr << "-------------------\n";
  }
} 

Compilation message (stderr)

abduction2.cpp: In function 'int G::startdfs(int)':
abduction2.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [a, b] : g[node])
      |              ^
abduction2.cpp: In function 'int start(int, int, bool, bool)':
abduction2.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto [coord, atrnode] : vec) {
      |              ^
abduction2.cpp:55:7: warning: unused variable 'node' [-Wunused-variable]
   55 |   int node;
      |       ^~~~

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56