Submission #760286

#	Time	Username	Problem	Language	Result	Execution time	Memory
760286		mgl_diamond	Toll (BOI17_toll)	C++14	0 / 100	33 ms	8640 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second

const int INF = 1e9;
const int N = 50005;
const int LOG = 17;
using dt = pair<ii, int>;

int k, n, m, o, ret[N];
int f[5][N], g[5][N];
vector<ii> go[N], back[N];
vector<dt> querys;

void divide(int lx, int rx, vector<dt> &ask) {
  if (ask.empty()) return;

  // cout << "From block " << lx << " to block " << rx << ":\n";
  // for(dt x : ask) cout << x.fi.fi << " " << x.fi.se << "\n";
  // cout << "---------\n";
  // centroid
  int mx = (lx+rx)/2;
  int st = lx*k, en = min(n, (rx+1)*k);
  
  // reset
  // cout << st << " " << en << "\n";
  for(int t=0; t<k; ++t) {
    for(int i=st; i<en; ++i) {
      f[t][i] = g[t][i] = INF;
    }
  }

  int l = mx*k, r = min(n, l+k);  

  // cout << g[0][12] << "\n";
  for(int m=l; m<r; ++m) {
    f[m-l][m] = g[m-l][m] = 0;

    for(int i=m; i>st; --i) {
      for(ii x : back[i]) {
        f[m-l][x.fi] = min(f[m-l][x.fi], f[m-l][i] + x.se);
      }
    }

    for(int i=m; i<en-1; ++i) {
      for(ii x : go[i]) {
        // if (i==5) cout << x.fi << " " << x.se <<
        g[m-l][x.fi] = min(g[m-l][x.fi], g[m-l][i] + x.se);
      }
    }
  }
  // cout << g[0][12] << "\n";

  // cout << f[0][0] << " " << g[0][12] << "\n";

  vector<dt> _left, _right;
  for(auto x : ask) {
    if (x.fi.se/k < lx) _left.emplace_back(x);
    else if (x.fi.fi/k > rx) _right.emplace_back(x);
    else {
      for(int m=l; m<r; ++m) {
        ret[x.se] = min(ret[x.se], f[m-l][x.fi.fi] + g[m-l][x.fi.se]);
      }
      // if (x.se == 1) cout << f[]
    }
  }

  divide(lx, mx-1, _left);
  divide(mx+1, rx, _right);
}

void solve() {
  cin >> k >> n >> m >> o;

  for(int i=1; i<=m; ++i) {
    int u, v, t;
    cin >> u >> v >> t;

    go[u].emplace_back(v, t);
    back[v].emplace_back(u, t);
  }

  for(int i=1; i<=o; ++i) {
    int u, v;
    cin >> u >> v;

    querys.push_back({{u, v}, i});
  }

  memset(ret, 0x3f, sizeof(ret));
  divide(0, (n-1)/k, querys);

  for(int i=1; i<=o; ++i) {
    if (ret[i] < INF) cout << ret[i] << "\n";
    else cout << "-1\n";
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
 
  if (fopen("input.inp", "r")) {
    freopen("input.inp", "r", stdin);
    freopen("input.out", "w", stdout);
  }
 
  solve();
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:112:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44