| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 333545 |
2020-12-07T00:00:06 Z |
gmyu |
Toll (BOI17_toll) |
C++14 |
|
422 ms |
190828 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
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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
190828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
422 ms |
106476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
3820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
3820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
190828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
