oj.uz

Submission #682612

# Submission time Handle Problem Language Result Execution time Memory
682612 2023-01-16T15:19:31 Z TS_2392 Toll (BOI17_toll) C++14
7 / 100
 73 ms 33724 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 * 5][17][5];
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 < 17; ++i){
            for(int j = 0; j < k; ++j) d[u][i][j] = oo;
        }
    }
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v >> d[u][0][v % k];
    }
    for(int i = 1; i < 17; ++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]);
        }
    }
    while(qsn--){
        int x, y, prefloor, lastfloor;
        cin >> x >> y;
        prefloor = x / k, lastfloor = y / k;
        if(prefloor < lastfloor){
            int delta = lastfloor - prefloor, fstbit = ctz(delta), msk = 0;
            delta -= 1 << fstbit; prefloor += 1 << fstbit;
            ll dist[2][k];
            for(int i = 0; i < k; ++i) dist[msk][i] = d[x][fstbit][i];
            for(int curbit = 0; curbit < 17; ++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(prefloor, ii)][curbit][i]);
                    }
                }
                prefloor += 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:60:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   60 |             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 48 ms 33724 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 44 ms 33592 KB Output is correct
9 Correct 47 ms 33612 KB Output is correct
10 Correct 28 ms 33632 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 33724 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 44 ms 33592 KB Output is correct
9 Correct 47 ms 33612 KB Output is correct
10 Correct 28 ms 33632 KB Output is correct
11 Incorrect 73 ms 33712 KB Output isn't correct
12 Halted 0 ms 0 KB -