| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 541587 |
2022-03-23T19:35:07 Z |
cadmiumsky |
Golf (JOI17_golf) |
C++14 |
|
22 ms |
6268 KB |
#include <bits/stdc++.h>
using namespace std;
namespace G { // nodul 0 este o santinela la care se pointeaza in mod inutil (i.e. cand stergi din AINT)
deque<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;
x = deq.front();
deq.pop_front();
//cerr << x << ' ' <<time[x] << '\n';
if(x == u || x == v)
return time[x];
for(auto [y, pt] : g[x]) {
if(time[y] == -1) {
time[y] = time[x] + pt;
//cerr << "---> " << y << ' ' <<time[y] << '\n';
if(pt == 0)
deq.push_front(y);
else
deq.push_back(y);
}
}
return bdfs();
}
int start(int S, int T, int U, int V) {
deq.push_back(S);
deq.push_back(T);
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;
int 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:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | 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:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [x1, y1, x2, y2] : squares) {
| ^
golf.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | for(auto [tlin, aaa, bbb] : forb) {
| ^
golf.cpp:74: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]
74 | while(temp < forb.size() && abs(get<0>(forb[temp])) < tlin) {
| ~~~~~^~~~~~~~~~~~~
golf.cpp:87: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]
87 | while(ptr < forb.size() && abs(get<0>(forb[ptr])) < tlin) {
| ~~~~^~~~~~~~~~~~~
golf.cpp:107: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]
107 | while(temp < forb.size()) {
| ~~~~~^~~~~~~~~~~~~
golf.cpp:120: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]
120 | while(ptr < forb.size()) {
| ~~~~^~~~~~~~~~~~~
golf.cpp:140:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
140 | for(auto &[a1, b1, c1, d1] : squares)
| ^
golf.cpp:145: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]
145 | 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:153:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | for(auto [poz, l, r, gid] : hor) { // init map
| ^
golf.cpp:158:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
158 | for(auto [poz, l, r, gid] : ver) {
| ^
golf.cpp:169:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
169 | for(auto &[poz, l, r, gid] : hor) { // set to normalization
| ^
golf.cpp:174:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
174 | for(auto &[poz, l, r, gid] : ver) {
| ^
golf.cpp: In function 'void MKG::AINT::update(int, int, int, int, int)':
golf.cpp:192:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
192 | int mid = cl + cr >> 1;
| ~~~^~~~
golf.cpp: In function 'void MKG::AINT::linkto(int, int, int, int, int, int)':
golf.cpp:208:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
208 | 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:222:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
222 | for(auto [poz, l, r, gid] : ver) {
| ^
golf.cpp:231:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
231 | for(auto [line, poz, gid] : qs) {
| ^
golf.cpp:232: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]
232 | while(ptr < hor.size() && get<0>(hor[ptr]) < abs(line)) {
| ~~~~^~~~~~~~~~~~
golf.cpp:245: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]
245 | while(ptr < hor.size()) {
| ~~~~^~~~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:265:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
265 | for(auto &[x1, y1, x2, y2] : squares)
| ^
golf.cpp:271:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
271 | for(auto [poz, l, r, gid] : hor) {
| ^
golf.cpp:277:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
277 | for(auto [poz, l, r, gid] : ver) {
| ^
golf.cpp:299:35: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
299 | cout << G::start(S, T, U, V) << '\n';
| ^~~~
golf.cpp:299:35: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:299:35: warning: 'V' may be used uninitialized in this function [-Wmaybe-uninitialized]
golf.cpp:299: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 |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
15 ms |
5760 KB |
Output is correct |
| 6 |
Correct |
19 ms |
5792 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 8 |
Correct |
15 ms |
5776 KB |
Output is correct |
| 9 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5740 KB |
Output is correct |
| 12 |
Correct |
16 ms |
5768 KB |
Output is correct |
| 13 |
Correct |
17 ms |
5740 KB |
Output is correct |
| 14 |
Correct |
15 ms |
5848 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1264 KB |
Output is correct |
| 16 |
Correct |
8 ms |
3084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
15 ms |
5760 KB |
Output is correct |
| 6 |
Correct |
19 ms |
5792 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 8 |
Correct |
15 ms |
5776 KB |
Output is correct |
| 9 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5740 KB |
Output is correct |
| 12 |
Correct |
16 ms |
5768 KB |
Output is correct |
| 13 |
Correct |
17 ms |
5740 KB |
Output is correct |
| 14 |
Correct |
15 ms |
5848 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1264 KB |
Output is correct |
| 16 |
Correct |
8 ms |
3084 KB |
Output is correct |
| 17 |
Correct |
21 ms |
6192 KB |
Output is correct |
| 18 |
Correct |
21 ms |
6248 KB |
Output is correct |
| 19 |
Incorrect |
22 ms |
6268 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
15 ms |
5760 KB |
Output is correct |
| 6 |
Correct |
19 ms |
5792 KB |
Output is correct |
| 7 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 8 |
Correct |
15 ms |
5776 KB |
Output is correct |
| 9 |
Correct |
14 ms |
5768 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
16 ms |
5740 KB |
Output is correct |
| 12 |
Correct |
16 ms |
5768 KB |
Output is correct |
| 13 |
Correct |
17 ms |
5740 KB |
Output is correct |
| 14 |
Correct |
15 ms |
5848 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1264 KB |
Output is correct |
| 16 |
Correct |
8 ms |
3084 KB |
Output is correct |
| 17 |
Correct |
21 ms |
6192 KB |
Output is correct |
| 18 |
Correct |
21 ms |
6248 KB |
Output is correct |
| 19 |
Incorrect |
22 ms |
6268 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
