Submission #333545

#	Time	Username	Problem	Language	Result	Execution time	Memory
333545		gmyu	Toll (BOI17_toll)	C++14	0 / 100	422 ms	190828 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

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// 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<pii, int> adjmap;

/**
* 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];
int rmq[18][5][MAXV][5];      /// 18 = ceil(log2(n))

int SecretLeft(int lev, int ly1, int ly2, int lym) {
    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++) {
                int w = MX;
                int a = PointsInLayer[ly1][i], b = PointsInLayer[ly2][k];
                if(adjmap.find(mp(a,b)) != adjmap.end()) w = adjmap[mp(a,b)];
                rmq[lev][j][ly1][i] = min(rmq[lev][j][ly1][i], w + rmq[lev][j][ly2][k]);
            }
        }
    }
}
int SecretRight(int lev, int lym, int ly2, int ly1) {
    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++) {
                int w = MX;
                int a = PointsInLayer[ly2][k], b = PointsInLayer[ly1][i];
                if(adjmap.find(mp(a,b)) != adjmap.end()) w = adjmap[mp(a,b)];
                rmq[lev][j][ly1][i] = min(rmq[lev][j][ly1][i], rmq[lev][j][ly2][k] + w);
            }
        }
    }
}
int SecretComb(int lev, int lym, int ly1, int ly2, int x1, int x2) {
    if(debug) cout << " .. combine " << ly1 << " " << ly2 << endl;
    int ans = MX;
    for(int i=0; i < PointsInLayer[lym].size(); i++) {
        int a = PointsInLayer[lym][i];
        for(int j=0; j < PointsInLayer[lym+1].size(); j++) {
            int b = PointsInLayer[lym+1][j];
            int w = MX;
            if(adjmap.find(mp(a,b)) != adjmap.end()) w = adjmap[mp(a,b)];
            ans = min(ans, rmq[lev][i][ly1][x1] + w + rmq[lev][j][ly2][x2]);
            if(debug) cout << " ...  cal point " << a << " -> " << b << " = " << rmq[lev][i][ly1][x1] << " + " << w << " + " << rmq[lev][j][ly2][x2] << " = " << ans << endl;
        }
    }
    return ans;
}

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=0; i < PointsInLayer[m+1].size(); i++) rmq[lev][i][m+1][i] = 0;
    for(int i = m+2; i <= r; i++) SecretRight(lev, m+1, i-1, i);

    divi(l,m,lev+1); divi(m+1,r,lev+1);
}
int 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 MX;
    int m = (l+r)/2;
    if(ql <= m && m+1 <= 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] = MX;
    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/K);
    for(i=0; i<M; i++) {
        int a, b, c; cin >> a >> b >> c;
        adjmap[mp(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;
        }
        int ans = que(ly1, ly2, x1, x2);
        if(ans >= MX) ans = -1;
        cout << ans << endl;
    }

}

Compilation message (stderr)

toll.cpp: In function 'int SecretLeft(int, int, int, int)':
toll.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int k=0; k < PointsInLayer[ly2].size(); k++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         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:74:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for(int j=0; j < PointsInLayer[lym].size(); j++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
   82 | }
      | ^
toll.cpp: In function 'int SecretRight(int, int, int, int)':
toll.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int k=0; k < PointsInLayer[ly2].size(); k++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         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:86:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for(int j=0; j < PointsInLayer[lym].size(); j++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:94:1: warning: no return statement in function returning non-void [-Wreturn-type]
   94 | }
      | ^
toll.cpp: In function 'int SecretComb(int, int, int, int, int, int)':
toll.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0; i < PointsInLayer[lym].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int j=0; j < PointsInLayer[lym+1].size(); j++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'void divi(int, int, int)':
toll.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0; i < PointsInLayer[m].size(); i++) rmq[lev][i][m][i] = 0;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i=0; i < PointsInLayer[m+1].size(); i++) rmq[lev][i][m+1][i] = 0;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'void insertLayer(int)':
toll.cpp:143:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int i = 0; !visited && i < PointsInLayer[ly].size(); i++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:169:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for(j=0; j<PointsInLayer[ly1].size(); j++) if(PointsInLayer[ly1][j] == a) x1 = j;
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:170:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         for(j=0; j<PointsInLayer[ly2].size(); j++) if(PointsInLayer[ly2][j] == b) x2 = j;
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:154:15: warning: unused variable 'k' [-Wunused-variable]
  154 |     int i, j, k;
      |               ^
toll.cpp: In function 'void setIO(std::string)':
toll.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44