oj.uz

Submission #682570

# Submission time Handle Problem Language Result Execution time Memory
682570 2023-01-16T14:27:43 Z TS_2392 Toll (BOI17_toll) C++14
7 / 100
 75 ms 41928 KB 
#include <bits/stdc++.h>
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define ctz(x) __builtin_ctz(x)
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sqr(x) (x) * (x)

#define eb emplace_back
#define epl emplace

#define lwb lower_bound
#define upb upper_bound

#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){
    if(a > b){a = b; return true;} return false;
}
template<class T1, class T2> bool maximize(T1 &a, T2 b){
    if(a < b){a = b; return true;} return false;
}
const int N = 5e4 + 3;
const ll oo = 1e10;
int k, m, n, qsn;
ll d[N * 3][17][6];
int real_id(int i, int j){
    return i * k + j;
}
int main(){
    SPEED; fileIO("");
    cin >> k >> n >> m >> qsn;
    for(int u = 0; u < n; ++u){
        for(int i = 0; i < 16; ++i){
            for(int j = 0; j < k; ++j) d[u][i][j] = oo;
        }
    }
    //cout << k << '\n';
    for(int i = 1; i <= m; ++i){
        //cout << i << ' ';
        int u, v;
        cin >> u >> v >> d[u][0][v % k];
        //cout << u << ' ' << v << ' ' << d[u][0][v % k] << '\n';
    }
    for(int i = 1; i < 16; ++i) for(int u = 0; u < n; ++u){
        for(int j = 0; j < k; ++j) for(int jj = 0; jj < k; ++jj){
            minimize(d[u][i][j], d[u][i - 1][jj] + d[real_id(u + (1 << i - 1), jj)][i - 1][j]);
        }
        //cout << i << ' ' << u << '\n';
    }
    //cout << 1 << '\n';
    while(qsn--){
        int x, y, flx, fly;
        cin >> x >> y;
        flx = x / k, fly = y / k;
        if(flx < fly){
            //cout << qsn << ' ' << x << ' ' << y << '\n';
            int delta = fly - flx, fstbit = ctz(delta), msk = 0;
            delta -= 1 << fstbit; flx += 1 << fstbit;
            ll dist[2][k];
            for(int i = 0; i < k; ++i) dist[0][i] = d[x][fstbit][i];
            for(int curbit = 0; curbit < 16; ++curbit) if(delta >> curbit & 1){
                msk ^= 1;
                for(int i = 0; i < k; ++i){
                    dist[msk][i] = oo;
                    for(int ii = 0; ii < k; ++ii){
                        minimize(dist[msk][i], dist[msk ^ 1][ii] + d[real_id(flx, ii)][curbit][i]);
                    }
                }
                flx += 1 << curbit;
            }
            cout << (dist[msk][y % k] < oo ? dist[msk][y % k] : -1) << '\n';
        }
        else cout << -1 << '\n';
    }
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:63:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |             minimize(d[u][i][j], d[u][i - 1][jj] + d[real_id(u + (1 << i - 1), jj)][i - 1][j]);
      |                                                                        ~~^~~
toll.cpp:2:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:47:12: note: in expansion of macro 'fileIO'
   47 |     SPEED; fileIO("");
      |            ^~~~~~
toll.cpp:2:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:47:12: note: in expansion of macro 'fileIO'
   47 |     SPEED; fileIO("");
      |            ^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41292 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 47 ms 41136 KB Output is correct
9 Correct 45 ms 41128 KB Output is correct
10 Correct 32 ms 40352 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41292 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 47 ms 41136 KB Output is correct
9 Correct 45 ms 41128 KB Output is correct
10 Correct 32 ms 40352 KB Output is correct
11 Incorrect 75 ms 41928 KB Output isn't correct
12 Halted 0 ms 0 KB -