| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 333564 |
2020-12-07T04:53:49 Z |
gmyu |
Toll (BOI17_toll) |
C++14 |
|
277 ms |
183916 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 = MX;
if(PointsInLayer[lym].size() == 0) return MX;
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 MX;
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/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;
}
int ans = que(ly1, ly2, x1, x2);
if(ans >= MX) 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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
183916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
97784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
4 ms |
4588 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4588 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
8172 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
4 ms |
4588 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4588 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
8172 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
183916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
