Submission #1171765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171765		farica	Toll (BOI17_toll)	C++20	100 / 100	84 ms	10056 KiB

toll

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
 
const int MOD = 1e9 + 7;
const int N = 1e6 + 5; 
 
template<ll mod>
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();
 
    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;
 
    S x;
 
    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }
 
    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
                        n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }
 
    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

template <class T> struct SegTree{
    vector<T> seg;
    int n;
    const T ID = 0;
    
    T cmb(T a, T b){
        return max(a,b);
    }
    
    SegTree(int _n){
        n = 1;
        while (n < _n) n *= 2;
        seg.assign(2 * n + 1, ID);
    }
    
    void set(int pos, T val){
        seg[pos + n] = val;
    }
    
    void build(){
        for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]);
    }
    
    void upd(int v, int tl, int tr, int pos, T val){
        if (tl == tr){
            seg[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) upd(2 * v, tl, tm, pos, val);
            else upd(2 * v + 1, tm + 1, tr, pos, val);
            seg[v] = cmb(seg[2 * v], seg[2 * v + 1]);
        }
    }
    
    void upd(int pos, T val){
        upd(1, 0, n - 1, pos, val);
            }
    
    T query(int v, int tl, int tr, int l, int r){
        if (l > r) return ID;
        if (l == tl && r == tr) return seg[v];
        int tm = (tl + tr) / 2;
        T res = query(2 * v, tl, tm, l, min(tm, r));
        res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        return res;
    }
    
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
};

struct DSU{
    vector<int> p, sz, used, mn, mx;
    
    DSU(int n){
        p.assign(n, 0);
        sz.assign(n, 1);
        used.assign(n, 0);
        mx.assign(n, 0);
        mn.assign(n, 0);
 
        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int find(int u){
        if (p[u] == u) return u;
        p[u] = find(p[u]);
        return p[u];
    }
        void unite(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return;
        
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        used[u] += used[v];
        mn[u] = min(mn[u], mn[v]);
        mx[u] = max(mx[u], mx[v]);
    }
    
    bool same(int u, int v){
        return find(u) == find(v);
    }
    
    int size(int u){
        u = find(u);
        return sz[u];
    }
};

struct BIT {
  int b[N], n;

  void init(int _n) {
    n = _n;
    for(int i = 0 ; i <= n ; ++i) b[i] = 0;
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, int v) {
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  int query(int x) {
    int ans = 0; 
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
} bit;

const int MX = 50005;
const int INF = 1e9;

int lft[5][MX], rght[5][MX], k, n;
vector<pi>Q, f[MX], g[MX];
vi ans;

void div1(int le, int ri, vi &v) {
	if(v.empty()) return;
	vi todo[2];
	int m = (le+ri)/2, st = le*k, en = min((ri+1)*k, n);
	for(int t=0; t<k; ++t) {
		for(int j=0; j<en; ++j) lft[t][j] = rght[t][j] = INF;
	}
	int l = m*k, r = min(n, l+k);
	for(int mx = l; mx < r; ++mx) {
		lft[mx-l][mx] = rght[mx-l][mx] = 0;
		for(int i=mx; i>st; --i) {
			for(pi x: g[i]) lft[mx-l][x.first] = min(lft[mx-l][x.first], lft[mx-l][i] + x.second);
		}
		for(int i=mx; i<en-1; ++i) {
			for(pi x: f[i]) rght[mx-l][x.first] = min(rght[mx-l][x.first], rght[mx-l][i] + x.second);
		}
	}
	for(int t: v) {
		int a = Q[t].first, b = Q[t].second;
		if(b/k < m) todo[0].push_back(t);
		else if(a/k > m) todo[1].push_back(t);
		else { 
			for(int mx = l; mx < r; ++mx) {
				if(ans[t] == -1) ans[t] = lft[mx-l][a] + rght[mx-l][b];
				else ans[t] = min(ans[t], lft[mx-l][a] + rght[mx-l][b]);
			}
		}
	}
	div1(le, m, todo[0]);
	div1(m+1, ri, todo[1]);
}

void solve() {
    int m, o;
    cin >> k >> n >> m >> o;
    while(m--) {
		int a, b, w;
		cin >> a >> b >> w;
		f[a].push_back({b,w});
		g[b].push_back({a,w});
	}
	vi v;
	for(int i=0; i<o; ++i) {
		v.push_back(i);
		int a, b;
		cin >> a >> b;
		Q.push_back({a,b});
	}
	ans.assign(o, -1);
	div1(0, (n-1)/k, v);
	for(int x: ans) {
		if(x >= INF) cout << -1 << endl;
		else cout << x << endl;
	}
}

int main(	){
	//freopen("input1.txt", "r", stdin)   
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	    
    int t = 1;
    while (t--) solve();
}

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