| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 541597 |
2022-03-23T19:58:02 Z |
cadmiumsky |
Golf (JOI17_golf) |
C++14 |
|
3792 ms |
995360 KB |
#include <bits/stdc++.h>
//#define int long long
using namespace std;
namespace G { // nodul 0 este o santinela la care se pointeaza in mod inutil (i.e. cand stergi din AINT)
deque<pair<int, int> > deq;
vector<int> time;
vector<vector<pair<int, int> > > g;
int push() { g.push_back(vector<pair<int, int> >()); return g.size() - 1; }
void push(int u, int v, int w) { // w ar trebui sa fie doar 1 sau 0
g[u].push_back({v, w});
g[v].push_back({u, w});
}
void pushdir(int u, int v, int w) { g[u].push_back({v, w}); }
int u, v;
int bdfs() {
if(deq.size() == 0)
return -1;
int x, t;
tie(x, t) = deq.front();
deq.pop_front();
if(t != time[x])
return bdfs();
//cerr << x << ' ' <<time[x] << '\n';
if(x == u || x == v)
return time[x];
for(auto [y, pt] : g[x]) {
if(time[y] > time[x] + pt || time[y] == -1) {
time[y] = time[x] + pt;
//cerr << "---> " << y << ' ' <<time[y] << '\n';
if(pt == 0)
deq.push_front({y, time[y]});
else
deq.push_back({y, time[y]});
}
}
return bdfs();
}
int start(int S, int T, int U, int V) {
deq.push_back({S, 1});
deq.push_back({T, 1});
tie(u, v) = {U, V};
time.resize(g.size(), -1);
time[S] = 1;
time[T] = 1;
return bdfs();
}
}
// x1, y1, x2, y2
vector<tuple<int,int,int,int> > squares;
namespace Norm {
multiset<int> app;
vector<tuple<int,int,int> > forb;
void make(vector<tuple<int,int,int,int> > &hor, int s, int t, int u, int v) {
for(auto [x1, y1, x2, y2] : squares) {
forb.emplace_back(x1, y1, y2);
forb.emplace_back(-x2, y1, y2);
}
forb.push_back({s, t, t});
forb.push_back({-s, t, t});
forb.push_back({-u, v, v});
forb.push_back({u, v, v});
sort(forb.begin(), forb.end(), [&](auto tp1, auto tp2) {
return abs(get<0>(tp1)) < abs(get<0>(tp2)) ||
(abs(get<0>(tp1)) == abs(get<0>(tp2)) && get<0>(tp1) > get<0>(tp2));
});
app.insert(0);
app.insert(1e9 + 1);
int ptr = 0, a, b, c, lin, col1, col2;
int temp;
for(auto [tlin, aaa, bbb] : forb) {
tlin = abs(tlin);
temp = ptr;
while(temp < forb.size() && abs(get<0>(forb[temp])) < tlin) {
tie(lin, col1, col2) = forb[temp];
if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
temp++;
continue;
}
if(lin < 0) {
app.erase(col1);
app.erase(col2);
}
temp++;
}
temp = ptr;
while(ptr < forb.size() && abs(get<0>(forb[ptr])) < tlin) {
tie(a, b, c) = forb[ptr];
auto it = app.upper_bound(b);
hor.push_back({abs(a), *prev(it), *it, G::push()});
ptr++;
}
while(temp < ptr) {
tie(lin, col1, col2) = forb[temp];
if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
temp++;
continue;
}
if(lin > 0) {
app.insert(col1);
app.insert(col2);
}
temp++;
}
}
temp = ptr;
while(temp < forb.size()) {
tie(lin, col1, col2) = forb[temp];
if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
temp++;
continue;
}
if(lin < 0) {
app.erase(col1);
app.erase(col2);
}
temp++;
}
temp = ptr;
while(ptr < forb.size()) {
tie(a, b, c) = forb[ptr];
auto it = app.upper_bound(b);
hor.push_back({abs(a), *prev(it), *it, G::push()});
ptr++;
}
while(temp < ptr) {
tie(lin, col1, col2) = forb[temp];
if((abs(lin) == s || abs(lin) == u) && col1 == col2) {
temp++;
continue;
}
if(lin > 0) {
app.insert(col1);
app.insert(col2);
}
temp++;
}
forb.clear();
app.clear();
for(auto &[a1, b1, c1, d1] : squares)
swap(a1, b1), swap(c1, d1);
sort(hor.begin(), hor.end());
vector<tuple<int,int,int,int> > thor;
thor.push_back(hor[0]);
for(int i = 1; i < hor.size(); i++) {
if(get<0>(hor[i]) != get<0>(hor[i - 1]) || get<1>(hor[i]) != get<1>(hor[i - 1]) || get<2>(hor[i]) != get<2>(hor[i - 1]))
thor.push_back(hor[i]);
}
hor = move(thor);
}
map<int,int> mp[2];
int normalize(vector<tuple<int,int,int,int>>& hor, vector<tuple<int,int,int,int>>& ver) {
for(auto [poz, l, r, gid] : hor) { // init map
mp[1][l];
mp[1][r];
mp[0][poz];
}
for(auto [poz, l, r, gid] : ver) {
mp[0][l];
mp[0][r];
mp[1][poz];
}
int cnt = 1;
for(auto &x : mp[0])
x.second = cnt++;
cnt = 1;
for(auto &x : mp[1])
x.second = cnt++;
for(auto &[poz, l, r, gid] : hor) { // set to normalization
poz = mp[0][poz];
l = mp[1][l];
r = mp[1][r];
}
for(auto &[poz, l, r, gid] : ver) {
poz = mp[1][poz];
l = mp[0][l];
r = mp[0][r];
}
return max(mp[0].size(), mp[1].size());
}
}
namespace MKG {
namespace AINT {
vector<int> aint;
int n;
void update(int poz, int gid, int node = 1, int cl = 1, int cr = n) {
if(cl == cr) {
aint[node] = gid;
return;
}
int mid = cl + cr >> 1;
if(poz <= mid)
update(poz, gid, 2 * node, cl, mid);
else
update(poz, gid, 2 * node + 1, mid + 1, cr);
aint[node] = G::push();
G::pushdir(aint[node], aint[2 * node], 0);
G::pushdir(aint[node], aint[2 * node + 1], 0);
}
void linkto(int gid, int l, int r, int node = 1, int cl = 1, int cr = n) {
if(r < cl || cr < l)
return;
if(l <= cl && cr <= r) {
G::pushdir(gid, aint[node], 1);
return;
}
int mid = cl + cr >> 1;
linkto(gid, l, r, 2 * node, cl, mid);
linkto(gid, l, r, 2 * node + 1, mid + 1, cr);
}
void reset(int nlen) {
n = nlen + 1;
aint.resize(n * 4);
}
}
void start(vector<tuple<int,int,int,int> > ver, vector<tuple<int,int,int,int> > hor, int ASIZE) {
AINT::reset(ASIZE);
// 1 1 1 -- add
// -1 1 1 -- erase
vector<tuple<int,int,int> > qs;
for(auto [poz, l, r, gid] : ver) {
qs.push_back({l, poz, gid});
qs.push_back({-r - 1, poz, gid});
}
sort(qs.begin(), qs.end(), [&](auto tp1, auto tp2) {
return abs(get<0>(tp1)) < abs(get<0>(tp2)) ||
(abs(get<0>(tp1)) == abs(get<0>(tp2)) && get<0>(tp1) < get<0>(tp2));
});
int ptr = 0, a, l, r, tempid;
for(auto [line, poz, gid] : qs) {
while(ptr < hor.size() && get<0>(hor[ptr]) < abs(line)) {
tie(a, l, r, tempid) = hor[ptr];
//cerr << tempid << ' '<< l << ' ' << r << '\n';
AINT::linkto(tempid, l, r);
ptr++;
}
if(line < 0)
//cerr << "- " << poz << ' '<< gid << '\n',
AINT::update(poz, 0);
else
//cerr << "+ " << poz << ' '<< gid << '\n',
AINT::update(poz, gid);
}
while(ptr < hor.size()) {
tie(a, l, r, tempid) = hor[ptr];
AINT::linkto(tempid, l, r);
//cerr << tempid << ' '<< l << ' ' << r << '\n';
ptr++;
}
//cerr << '\n';
return;
}
}
// poz, [l, r], graphID
vector<tuple<int,int,int,int> > hor, ver;
signed main() {
int n;
int s, t, u, v;
cin >> s >> t >> u >> v >> n;
squares.resize(n);
for(auto &[x1, y1, x2, y2] : squares)
cin >> x1 >> x2 >> y1 >> y2;
G::push();
Norm::make(hor, s, t, u, v);
Norm::make(ver, t, s, v, u);
int S, T, U, V;
for(auto [poz, l, r, gid] : hor) {
if(poz == s && l <= t && t <= r)
T = gid;
if(poz == u && l <= v && v <= r)
V = gid;
}
for(auto [poz, l, r, gid] : ver) {
if(poz == t && l <= s && s <= r)
S = gid;
if(poz == v && l <= u && u <= r)
U = gid;
}
//cerr << "Horisontal:\n";
//for(auto [line, l, r, gid] : hor)
//cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
//cerr << "Vertical:\n";
//for(auto [line, l, r, gid] : ver)
//cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
int ASIZE = Norm::normalize(hor, ver);
//cerr << "Horisontal:\n";
//for(auto [line, l, r, gid] : hor)
//cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
//cerr << "Vertical:\n";
//for(auto [line, l, r, gid] : ver)
//cerr << line <<' ' << l << ' '<< r << ' ' << gid << '\n';
//cerr << "</>" << S << ' ' << T << ' ' << U << ' ' << V << '\n';
MKG::start(ver, hor, ASIZE);
MKG::start(hor, ver, ASIZE);
cout << G::start(S, T, U, V) << '\n';
}
Compilation message
golf.cpp: In function 'int G::bdfs()':
golf.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for(auto [y, pt] : g[x]) {
| ^
golf.cpp: In function 'void Norm::make(std::vector<std::tuple<int, int, int, int> >&, int, int, int, int)':
golf.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for(auto [x1, y1, x2, y2] : squares) {
| ^
golf.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
73 | for(auto [tlin, aaa, bbb] : forb) {
| ^
golf.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while(temp < forb.size() && abs(get<0>(forb[temp])) < tlin) {
| ~~~~~^~~~~~~~~~~~~
golf.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | while(ptr < forb.size() && abs(get<0>(forb[ptr])) < tlin) {
| ~~~~^~~~~~~~~~~~~
golf.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | while(temp < forb.size()) {
| ~~~~~^~~~~~~~~~~~~
golf.cpp:122:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while(ptr < forb.size()) {
| ~~~~^~~~~~~~~~~~~
golf.cpp:142:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | for(auto &[a1, b1, c1, d1] : squares)
| ^
golf.cpp:147:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 1; i < hor.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp: In function 'int Norm::normalize(std::vector<std::tuple<int, int, int, int> >&, std::vector<std::tuple<int, int, int, int> >&)':
golf.cpp:155:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
155 | for(auto [poz, l, r, gid] : hor) { // init map
| ^
golf.cpp:160:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
160 | for(auto [poz, l, r, gid] : ver) {
| ^
golf.cpp:171:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
171 | for(auto &[poz, l, r, gid] : hor) { // set to normalization
| ^
golf.cpp:176:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
176 | for(auto &[poz, l, r, gid] : ver) {
| ^
golf.cpp: In function 'void MKG::AINT::update(int, int, int, int, int)':
golf.cpp:194:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
194 | int mid = cl + cr >> 1;
| ~~~^~~~
golf.cpp: In function 'void MKG::AINT::linkto(int, int, int, int, int, int)':
golf.cpp:210:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
210 | int mid = cl + cr >> 1;
| ~~~^~~~
golf.cpp: In function 'void MKG::start(std::vector<std::tuple<int, int, int, int> >, std::vector<std::tuple<int, int, int, int> >, int)':
golf.cpp:224:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
224 | for(auto [poz, l, r, gid] : ver) {
| ^
golf.cpp:233:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
233 | for(auto [line, poz, gid] : qs) {
| ^
golf.cpp:234:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
234 | while(ptr < hor.size() && get<0>(hor[ptr]) < abs(line)) {
| ~~~~^~~~~~~~~~~~
golf.cpp:247:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | while(ptr < hor.size()) {
| ~~~~^~~~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:267:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
267 | for(auto &[x1, y1, x2, y2] : squares)
| ^
golf.cpp:273:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
273 | for(auto [poz, l, r, gid] : hor) {
| ^
golf.cpp:279:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
279 | for(auto [poz, l, r, gid] : ver) {
| ^
golf.cpp:301:35: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
301 | cout << G::start(S, T, U, V) << '\n';
| ^~~~
golf.cpp:301:35: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:301:35: warning: 'V' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:301:35: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
16 ms |
5768 KB |
Output is correct |
| 6 |
Correct |
21 ms |
5768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 9 |
Correct |
15 ms |
5780 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5968 KB |
Output is correct |
| 12 |
Correct |
14 ms |
5720 KB |
Output is correct |
| 13 |
Correct |
21 ms |
5828 KB |
Output is correct |
| 14 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1296 KB |
Output is correct |
| 16 |
Correct |
7 ms |
3084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
16 ms |
5768 KB |
Output is correct |
| 6 |
Correct |
21 ms |
5768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 9 |
Correct |
15 ms |
5780 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5968 KB |
Output is correct |
| 12 |
Correct |
14 ms |
5720 KB |
Output is correct |
| 13 |
Correct |
21 ms |
5828 KB |
Output is correct |
| 14 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1296 KB |
Output is correct |
| 16 |
Correct |
7 ms |
3084 KB |
Output is correct |
| 17 |
Correct |
25 ms |
6244 KB |
Output is correct |
| 18 |
Correct |
21 ms |
6148 KB |
Output is correct |
| 19 |
Correct |
21 ms |
6276 KB |
Output is correct |
| 20 |
Correct |
19 ms |
6256 KB |
Output is correct |
| 21 |
Correct |
19 ms |
6404 KB |
Output is correct |
| 22 |
Correct |
19 ms |
6404 KB |
Output is correct |
| 23 |
Correct |
20 ms |
6264 KB |
Output is correct |
| 24 |
Correct |
20 ms |
6276 KB |
Output is correct |
| 25 |
Correct |
18 ms |
6344 KB |
Output is correct |
| 26 |
Correct |
19 ms |
6304 KB |
Output is correct |
| 27 |
Correct |
4 ms |
1680 KB |
Output is correct |
| 28 |
Correct |
8 ms |
3084 KB |
Output is correct |
| 29 |
Correct |
9 ms |
3084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
16 ms |
5768 KB |
Output is correct |
| 6 |
Correct |
21 ms |
5768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 9 |
Correct |
15 ms |
5780 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5968 KB |
Output is correct |
| 12 |
Correct |
14 ms |
5720 KB |
Output is correct |
| 13 |
Correct |
21 ms |
5828 KB |
Output is correct |
| 14 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1296 KB |
Output is correct |
| 16 |
Correct |
7 ms |
3084 KB |
Output is correct |
| 17 |
Correct |
25 ms |
6244 KB |
Output is correct |
| 18 |
Correct |
21 ms |
6148 KB |
Output is correct |
| 19 |
Correct |
21 ms |
6276 KB |
Output is correct |
| 20 |
Correct |
19 ms |
6256 KB |
Output is correct |
| 21 |
Correct |
19 ms |
6404 KB |
Output is correct |
| 22 |
Correct |
19 ms |
6404 KB |
Output is correct |
| 23 |
Correct |
20 ms |
6264 KB |
Output is correct |
| 24 |
Correct |
20 ms |
6276 KB |
Output is correct |
| 25 |
Correct |
18 ms |
6344 KB |
Output is correct |
| 26 |
Correct |
19 ms |
6304 KB |
Output is correct |
| 27 |
Correct |
4 ms |
1680 KB |
Output is correct |
| 28 |
Correct |
8 ms |
3084 KB |
Output is correct |
| 29 |
Correct |
9 ms |
3084 KB |
Output is correct |
| 30 |
Correct |
3147 ms |
919540 KB |
Output is correct |
| 31 |
Correct |
3154 ms |
919456 KB |
Output is correct |
| 32 |
Correct |
3541 ms |
929936 KB |
Output is correct |
| 33 |
Correct |
3656 ms |
929188 KB |
Output is correct |
| 34 |
Correct |
3090 ms |
939332 KB |
Output is correct |
| 35 |
Correct |
3792 ms |
939388 KB |
Output is correct |
| 36 |
Correct |
3084 ms |
939272 KB |
Output is correct |
| 37 |
Correct |
3392 ms |
939444 KB |
Output is correct |
| 38 |
Correct |
3280 ms |
939428 KB |
Output is correct |
| 39 |
Correct |
3477 ms |
939756 KB |
Output is correct |
| 40 |
Correct |
2201 ms |
974368 KB |
Output is correct |
| 41 |
Correct |
2196 ms |
974224 KB |
Output is correct |
| 42 |
Correct |
2302 ms |
984928 KB |
Output is correct |
| 43 |
Correct |
2171 ms |
960068 KB |
Output is correct |
| 44 |
Correct |
2257 ms |
970312 KB |
Output is correct |
| 45 |
Correct |
2223 ms |
970292 KB |
Output is correct |
| 46 |
Correct |
2175 ms |
970484 KB |
Output is correct |
| 47 |
Correct |
2236 ms |
970384 KB |
Output is correct |
| 48 |
Correct |
2206 ms |
995360 KB |
Output is correct |
| 49 |
Correct |
2224 ms |
995304 KB |
Output is correct |
| 50 |
Correct |
9 ms |
3076 KB |
Output is correct |
| 51 |
Correct |
9 ms |
3132 KB |
Output is correct |
| 52 |
Correct |
10 ms |
3084 KB |
Output is correct |
