oj.uz

Submission #874091

# Submission time Handle Problem Language Result Execution time Memory
874091 2023-11-16T09:06:37 Z hqminhuwu Toll (BOI17_toll) C++14
7 / 100
 97 ms 304912 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <ll,pii>
#define vi vector <ll>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const ll N = 5e5 + 5;
const ll oo = 1e17;
const ll mod = 1e9 + 7;

inline void mnmize (ll &u, ll v){
    if (u > v)
        u = v;
}

ll n,m,x,q,u,v,w,i,up[20][100005][6][6],j,k,g,l;
vector <pii> a[N];
ll res[6][6],nres[6][6];
void jump (ll u, ll d){
    forr (l,0,18)
    if ((1 << l) & d){
        forf (i,0,x)
        forf (j,0,x)
            nres[i][j] = oo;
        forf (i,0,x)
        forf (j,0,x)
        forf (k,0,x)
            mnmize (nres[i][k],res[i][j] + up[l][u][j][k]);
        swap(res,nres);
        u += (1 << l);
        //cout << u << " " << res[0][0] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> x >> n >> m >> q;
    ll bl = n / x + 1;
    forr (i,1,m){
        cin >> u >> v >> w;
        a[u].pb({v,w});
    }
    forr (l,0,18)
    forr (i,0,bl)
    forf (j,0,x)
    forf (k,0,x)
        up[l][i][j][k] = oo;
    forr (i,0,bl)
    forf (j,0,x)
    for (pii v : a[i * x + j]){
        mnmize (up[0][i][j][v.st % x],v.nd);
    }
    forr (l,1,18)
    forr (i,0,bl){
        ll f = i + (1 << (l - 1)); 
        forf (j,0,x) 
        forf (k,0,x)
        forf (g,0,x)
            mnmize (up[l][i][j][g],up[l - 1][i][j][k] + up[l - 1][f][k][g]);
    }
    while (q--){
        ll b,c;
        cin >> b >> c;
        memset(res,0,sizeof res);
        //cout << b/x << " " << c/x << " " << b % x << " " << c % x << "\n";
        jump(b/x, c/x - b/x);
        if (res[b % x][c % x] < oo && b / x != c / x)
            cout << res[b % x][c % x] << "\n";
        else cout << "-1\n";
    }
    return 0;
}
/*



*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 304912 KB Output is correct
2 Correct 6 ms 49752 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 7 ms 49764 KB Output is correct
5 Correct 8 ms 53852 KB Output is correct
6 Correct 8 ms 53852 KB Output is correct
7 Correct 8 ms 53852 KB Output is correct
8 Correct 93 ms 304856 KB Output is correct
9 Correct 97 ms 304908 KB Output is correct
10 Correct 80 ms 303340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 187820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 49832 KB Output is correct
2 Incorrect 7 ms 49752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 49832 KB Output is correct
2 Incorrect 7 ms 49752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 304912 KB Output is correct
2 Correct 6 ms 49752 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 7 ms 49764 KB Output is correct
5 Correct 8 ms 53852 KB Output is correct
6 Correct 8 ms 53852 KB Output is correct
7 Correct 8 ms 53852 KB Output is correct
8 Correct 93 ms 304856 KB Output is correct
9 Correct 97 ms 304908 KB Output is correct
10 Correct 80 ms 303340 KB Output is correct
11 Incorrect 72 ms 187820 KB Output isn't correct
12 Halted 0 ms 0 KB -