Submission #333569

#	Time	Username	Problem	Language	Result	Execution time	Memory
333569		gmyu	Toll (BOI17_toll)	C++14	100 / 100	625 ms	184940 KiB

toll

/*
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;
    if(PointsInLayer[m].size() >0) {
        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;
    if(PointsInLayer[lym].size() == 0) return INF;
    ll ans = 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 (stderr)

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:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         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:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0; i < PointsInLayer[lym].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:102:13: warning: unused variable 'a' [-Wunused-variable]
  102 |         int a = PointsInLayer[lym][i];
      |             ^
toll.cpp: In function 'void insertLayer(int)':
toll.cpp:128:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i = 0; !visited && (i < PointsInLayer[ly].size() ); i++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for(j=0; j<PointsInLayer[ly1].size(); j++) if(PointsInLayer[ly1][j] == a) x1 = j;
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for(j=0; j<PointsInLayer[ly2].size(); j++) if(PointsInLayer[ly2][j] == b) x2 = j;
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:139:15: warning: unused variable 'k' [-Wunused-variable]
  139 |     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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44