Submission #333567

#TimeUsernameProblemLanguageResultExecution timeMemory
333567gmyuToll (BOI17_toll)C++14
100 / 100
613 ms184944 KiB
/* 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 (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: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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...