oj.uz

Submission #333567

# Submission time Handle Problem Language Result Execution time Memory
333567 2020-12-07T04:59:13 Z gmyu Toll (BOI17_toll) C++14
100 / 100
 613 ms 184944 KB 
/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 50007
#define MAXE 100007


/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

int K, N, M, O;
vi PointsInLayer[MAXV];
map<int, int> adjmap[MAXV];

/**
* RMQ use sparse table, O(N log N) memory and setip, O(1) query
* https://usaco.guide/plat/DC-SRQ
* example problem: https://oj.uz/problem/view/JOI14_secret
*/
int rmqN, rmqRange[2];
int rmqX[MAXV];
ll rmq[18][5][MAXV][5];      /// 18 = ceil(log2(n))

void SecretLeft(int lev, int ly1, int ly2, int lym) {
    if(PointsInLayer[ly1].size() == 0 ||  PointsInLayer[ly2].size() == 0 || PointsInLayer[lym].size() == 0 ) return;
    for(int k=0; k < PointsInLayer[ly2].size(); k++) {
        for(int i=0; i < PointsInLayer[ly1].size(); i++) {    /// assume no layer is empty (otherwise no way to go from front to end
            for(int j=0; j < PointsInLayer[lym].size(); j++) {
                ll w = INF;
                int a = PointsInLayer[ly1][i], b = PointsInLayer[ly2][k];
                if(adjmap[a].find(b) != adjmap[a].end()) w = adjmap[a][b];
                rmq[lev][j][ly1][i] = min(rmq[lev][j][ly1][i], w + rmq[lev][j][ly2][k]);
            }
        }
    }
}
void SecretRight(int lev, int lym, int ly2, int ly1) {
    if(PointsInLayer[ly1].size() == 0 ||  PointsInLayer[ly2].size() == 0 || PointsInLayer[lym].size() == 0 ) return;
    for(int k=0; k < PointsInLayer[ly2].size(); k++) {
        for(int i=0; i < PointsInLayer[ly1].size(); i++) {    /// assume no layer is empty (otherwise no way to go from front to end
            for(int j=0; j < PointsInLayer[lym].size(); j++) {
                ll w = INF;
                int a = PointsInLayer[ly2][k], b = PointsInLayer[ly1][i];
                if(adjmap[a].find(b) != adjmap[a].end()) w = adjmap[a][b];
                rmq[lev][j][ly1][i] = min(rmq[lev][j][ly1][i], rmq[lev][j][ly2][k] + w);
            }
        }
    }
}
void divi(int l = rmqRange[0], int r = rmqRange[1], int lev = 0) { // generate dat and mask
    if(debug) cout << " build " << l << "," << r << endl;
    if (l >= r) { return; }
    int m = (l+r)/2;
    for(int i=0; i < PointsInLayer[m].size(); i++) rmq[lev][i][m][i] = 0;
    for(int i = m-1; i >= l; i--) SecretLeft(lev, i, i+1, m);
    for(int i = m+1; i <= r; i++) SecretRight(lev, m, i-1, i);

    divi(l,m,lev+1); divi(m+1,r,lev+1);
}
ll SecretComb(int lev, int lym, int ly1, int ly2, int x1, int x2) {
    if(debug) cout << " .. combine " << ly1 << " " << ly2 << endl;
    ll ans = INF;
    if(PointsInLayer[lym].size() == 0) return INF;
    for(int i=0; i < PointsInLayer[lym].size(); i++) {
        int a = PointsInLayer[lym][i];
        ans = min(ans, rmq[lev][i][ly1][x1] + rmq[lev][i][ly2][x2]);
        if(debug) cout << " ...  cal point " << rmq[lev][i][ly1][x1] << " + " << rmq[lev][i][ly2][x2] << " = " << ans << endl;
    }
    return ans;
}
ll que(int ql, int qr, int x1, int x2, int lev = 0, int l = rmqRange[0], int r = rmqRange[1]) {         /// [ , ]
    if(debug) cout << " que " << ql << "," << qr << " within " << l << "," << r << endl;
    if(l == r) return INF;
    int m = (l+r)/2;
    if(ql <= m && m <= qr) return SecretComb(lev, m, ql, qr, x1, x2);
    if(qr <= m) return que(ql, qr, x1, x2, lev+1, l, m);
    else return que(ql, qr, x1, x2, lev+1, m+1, r);
}
void Init() {
    for(int i=0; i<18; i++)
        for(int j=0; j<5; j++)
            for(int k=0; k<= rmqRange[1]; k++)
                for(int l=0; l<5; l++)
                    rmq[i][j][k][l] = INF;
    divi();
}

void insertLayer (int x) {
    int ly = (int)(x/K);
    bool visited = false;
    for(int i = 0; !visited && (i < PointsInLayer[ly].size() ); i++) {
        if(PointsInLayer[ly][i] == x) visited = true;
    }
    if(!visited) PointsInLayer[ly].pb(x);
    //rmqRange[0] = min(rmqRange[0], ly); rmqRange[1] = max(rmqRange[1], ly);
}

int main() {
    debug = false; submit = false;
    if(submit) setIO("testName");

    int i, j, k;

    cin >> K >> N >> M >> O ;
    rmqRange[0] = 0; rmqRange[1] = (int)((N-1)/K);
    for(i=0; i<M; i++) {
        int a, b, c; cin >> a >> b >> c;
        adjmap[a][b] = c;
        insertLayer(a); insertLayer(b);
    }
    Init();

    for(i=0; i<O; i++) {
        int a, b; cin >> a >> b;
        int ly1 = (int)(a/K), ly2 = (int)(b/K);
        int x1 = -1 , x2 = -1;
        for(j=0; j<PointsInLayer[ly1].size(); j++) if(PointsInLayer[ly1][j] == a) x1 = j;
        for(j=0; j<PointsInLayer[ly2].size(); j++) if(PointsInLayer[ly2][j] == b) x2 = j;
        if(ly1 >= ly2 || x1 == -1 || x2 == -1) {
            cout << -1 << endl;
            continue;
        }
        ll ans = que(ly1, ly2, x1, x2);
        if(ans >= INF) ans = -1;
        cout << ans << endl;
    }

}

Compilation message

toll.cpp: In function 'void SecretLeft(int, int, int, int)':
toll.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int k=0; k < PointsInLayer[ly2].size(); k++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i=0; i < PointsInLayer[ly1].size(); i++) {    /// assume no layer is empty (otherwise no way to go from front to end
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:63:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(int j=0; j < PointsInLayer[lym].size(); j++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'void SecretRight(int, int, int, int)':
toll.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int k=0; k < PointsInLayer[ly2].size(); k++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:75:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0; i < PointsInLayer[ly1].size(); i++) {    /// assume no layer is empty (otherwise no way to go from front to end
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:76:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int j=0; j < PointsInLayer[lym].size(); j++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'void divi(int, int, int)':
toll.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0; i < PointsInLayer[m].size(); i++) rmq[lev][i][m][i] = 0;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'll SecretComb(int, int, int, int, int, int)':
toll.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0; i < PointsInLayer[lym].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:100:13: warning: unused variable 'a' [-Wunused-variable]
  100 |         int a = PointsInLayer[lym][i];
      |             ^
toll.cpp: In function 'void insertLayer(int)':
toll.cpp:126:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int i = 0; !visited && (i < PointsInLayer[ly].size() ); i++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:152:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(j=0; j<PointsInLayer[ly1].size(); j++) if(PointsInLayer[ly1][j] == a) x1 = j;
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:153:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for(j=0; j<PointsInLayer[ly2].size(); j++) if(PointsInLayer[ly2][j] == b) x2 = j;
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:137:15: warning: unused variable 'k' [-Wunused-variable]
  137 |     int i, j, k;
      |               ^
toll.cpp: In function 'void setIO(std::string)':
toll.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 184172 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 3 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 9 ms 8172 KB Output is correct
7 Correct 10 ms 8172 KB Output is correct
8 Correct 223 ms 184944 KB Output is correct
9 Correct 215 ms 184812 KB Output is correct
10 Correct 129 ms 180204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 97772 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 4 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 3 ms 4588 KB Output is correct
7 Correct 35 ms 8300 KB Output is correct
8 Correct 34 ms 6636 KB Output is correct
9 Correct 217 ms 184812 KB Output is correct
10 Correct 392 ms 72428 KB Output is correct
11 Correct 293 ms 99692 KB Output is correct
12 Correct 268 ms 68460 KB Output is correct
13 Correct 444 ms 35512 KB Output is correct
14 Correct 214 ms 45800 KB Output is correct
15 Correct 252 ms 30852 KB Output is correct
16 Correct 268 ms 30828 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4588 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 3 ms 4588 KB Output is correct
4 Correct 3 ms 4588 KB Output is correct
5 Correct 3 ms 4588 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 7 ms 6380 KB Output is correct
8 Correct 16 ms 5484 KB Output is correct
9 Correct 9 ms 5612 KB Output is correct
10 Correct 194 ms 184812 KB Output is correct
11 Correct 262 ms 99308 KB Output is correct
12 Correct 365 ms 72300 KB Output is correct
13 Correct 403 ms 73196 KB Output is correct
14 Correct 323 ms 70764 KB Output is correct
15 Correct 242 ms 30828 KB Output is correct
16 Correct 245 ms 30700 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4588 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 3 ms 4588 KB Output is correct
4 Correct 3 ms 4588 KB Output is correct
5 Correct 3 ms 4588 KB Output is correct
6 Correct 7 ms 8172 KB Output is correct
7 Correct 7 ms 6380 KB Output is correct
8 Correct 16 ms 5484 KB Output is correct
9 Correct 9 ms 5612 KB Output is correct
10 Correct 194 ms 184812 KB Output is correct
11 Correct 262 ms 99308 KB Output is correct
12 Correct 365 ms 72300 KB Output is correct
13 Correct 403 ms 73196 KB Output is correct
14 Correct 323 ms 70764 KB Output is correct
15 Correct 242 ms 30828 KB Output is correct
16 Correct 245 ms 30700 KB Output is correct
17 Correct 268 ms 99308 KB Output is correct
18 Correct 3 ms 4588 KB Output is correct
19 Correct 3 ms 4588 KB Output is correct
20 Correct 3 ms 4588 KB Output is correct
21 Correct 3 ms 4588 KB Output is correct
22 Correct 3 ms 4588 KB Output is correct
23 Correct 15 ms 8172 KB Output is correct
24 Correct 15 ms 6508 KB Output is correct
25 Correct 20 ms 5612 KB Output is correct
26 Correct 17 ms 5612 KB Output is correct
27 Correct 199 ms 184812 KB Output is correct
28 Correct 384 ms 72300 KB Output is correct
29 Correct 404 ms 73196 KB Output is correct
30 Correct 331 ms 70892 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 184172 KB Output is correct
2 Correct 3 ms 4588 KB Output is correct
3 Correct 3 ms 4588 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 9 ms 8172 KB Output is correct
6 Correct 9 ms 8172 KB Output is correct
7 Correct 10 ms 8172 KB Output is correct
8 Correct 223 ms 184944 KB Output is correct
9 Correct 215 ms 184812 KB Output is correct
10 Correct 129 ms 180204 KB Output is correct
11 Correct 281 ms 97772 KB Output is correct
12 Correct 3 ms 4588 KB Output is correct
13 Correct 4 ms 4588 KB Output is correct
14 Correct 4 ms 4588 KB Output is correct
15 Correct 4 ms 4588 KB Output is correct
16 Correct 3 ms 4588 KB Output is correct
17 Correct 35 ms 8300 KB Output is correct
18 Correct 34 ms 6636 KB Output is correct
19 Correct 217 ms 184812 KB Output is correct
20 Correct 392 ms 72428 KB Output is correct
21 Correct 293 ms 99692 KB Output is correct
22 Correct 268 ms 68460 KB Output is correct
23 Correct 444 ms 35512 KB Output is correct
24 Correct 214 ms 45800 KB Output is correct
25 Correct 252 ms 30852 KB Output is correct
26 Correct 268 ms 30828 KB Output is correct
27 Correct 3 ms 4588 KB Output is correct
28 Correct 3 ms 4588 KB Output is correct
29 Correct 3 ms 4588 KB Output is correct
30 Correct 3 ms 4588 KB Output is correct
31 Correct 3 ms 4588 KB Output is correct
32 Correct 7 ms 8172 KB Output is correct
33 Correct 7 ms 6380 KB Output is correct
34 Correct 16 ms 5484 KB Output is correct
35 Correct 9 ms 5612 KB Output is correct
36 Correct 194 ms 184812 KB Output is correct
37 Correct 262 ms 99308 KB Output is correct
38 Correct 365 ms 72300 KB Output is correct
39 Correct 403 ms 73196 KB Output is correct
40 Correct 323 ms 70764 KB Output is correct
41 Correct 242 ms 30828 KB Output is correct
42 Correct 245 ms 30700 KB Output is correct
43 Correct 268 ms 99308 KB Output is correct
44 Correct 3 ms 4588 KB Output is correct
45 Correct 3 ms 4588 KB Output is correct
46 Correct 3 ms 4588 KB Output is correct
47 Correct 3 ms 4588 KB Output is correct
48 Correct 3 ms 4588 KB Output is correct
49 Correct 15 ms 8172 KB Output is correct
50 Correct 15 ms 6508 KB Output is correct
51 Correct 20 ms 5612 KB Output is correct
52 Correct 17 ms 5612 KB Output is correct
53 Correct 199 ms 184812 KB Output is correct
54 Correct 384 ms 72300 KB Output is correct
55 Correct 404 ms 73196 KB Output is correct
56 Correct 331 ms 70892 KB Output is correct
57 Correct 613 ms 61548 KB Output is correct
58 Correct 221 ms 184812 KB Output is correct
59 Correct 296 ms 99820 KB Output is correct