| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 711015 |
2023-03-16T07:13:23 Z |
EthanKim8683 |
Walk (CEOI06_walk) |
C++17 |
|
1000 ms |
109392 KB |
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const Lli MAX=1e18;
const I LOC=3,DES=4,LDC=5,DLC=6,ADD=1,REM=2;
tuple<I,I,I,I>rcts[N];
vector<tuple<I,I,I>>ques;
map<I,I>curs;
map<pair<I,I>,vector<pair<I,I>>>adjs;
priority_queue<pair<Lli,pair<I,I>>>djks;
map<pair<I,I>,pair<Lli,pair<I,I>>>diss;
vector<pair<I,I>>ress;
void add(pair<I,I>a,pair<Lli,pair<I,I>>dis){
if(!diss.count(a))diss[a]={MAX,{-1,-1}};
if(dis.first>=diss[a].first)return;
djks.push({-(diss[a]=dis).first,a});
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I x,y;cin>>x>>y;
I n;cin>>n;
for(I i=0;i<n;i++){
I x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
rcts[i]={x1-1,y1-1,x2+1,y2+1};
}
ques.push_back({-0,LOC,-1});
ques.push_back({-0,LDC,-1});
ques.push_back({-x,DLC,-1});
ques.push_back({-x,DES,-1});
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
ques.push_back({-x1,ADD,i});
ques.push_back({-x2,REM,i});
}
sort(ques.begin(),ques.end());
while(ques.size()){
auto[cur,t,i]=ques.back();ques.pop_back();
if(t==LOC){
if(curs.count(0)){
pair<I,I>a={curs[0],0},b={0,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,0});
}
if(t==DES){
if(curs.count(y)){
pair<I,I>a={curs[y],y},b={x,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({y,x});
}
if(t==LDC){
if(curs.count(y)){
pair<I,I>a={curs[y],y},b={0,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({y,0});
}
if(t==DLC){
if(curs.count(0)){
pair<I,I>a={curs[0],0},b={x,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,x});
}
if(t==ADD){
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(y1);
auto upp=curs.upper_bound(y2);
for(auto it=low;it!=upp;){
auto[y,x]=*it;
pair<I,I>a={x,y},b={x1,y};
pair<I,I>c={x1,y1},d={x1,y2};
if(a!=b){
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(b!=c){
adjs[b].push_back(c);
adjs[c].push_back(b);
}
if(b!=d){
adjs[b].push_back(d);
adjs[d].push_back(b);
}
it=curs.erase(it);
}
curs.insert({y1,x1});
curs.insert({y2,x1});
}
if(t==REM){
auto[x1,y1,x2,y2]=rcts[i];
if(curs.count(y1)){
pair<I,I>a={curs[y1],y1},b={x2,y1};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(curs.count(y2)){
pair<I,I>a={curs[y2],y2},b={x2,y2};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({y1,x2});
curs.insert({y2,x2});
}
}
curs.clear();
ques.push_back({-0,LOC,-1});
ques.push_back({-y,LDC,-1});
ques.push_back({-0,DLC,-1});
ques.push_back({-y,DES,-1});
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
ques.push_back({-y1,ADD,i});
ques.push_back({-y2,REM,i});
}
sort(ques.begin(),ques.end());
while(ques.size()){
auto[cur,t,i]=ques.back();ques.pop_back();
if(t==LOC){
if(curs.count(0)){
pair<I,I>a={0,curs[0]},b={0,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,0});
}
if(t==DES){
if(curs.count(x)){
pair<I,I>a={x,curs[x]},b={x,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({x,y});
}
if(t==LDC){
if(curs.count(0)){
pair<I,I>a={0,curs[0]},b={0,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,y});
}
if(t==DLC){
if(curs.count(x)){
pair<I,I>a={x,curs[x]},b={x,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({x,0});
}
if(t==ADD){
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(x1);
auto upp=curs.upper_bound(x2);
for(auto it=low;it!=upp;){
auto[x,y]=*it;
pair<I,I>a={x,y},b={x,y1};
pair<I,I>c={x1,y1},d={x2,y1};
if(a!=b){
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(b!=c){
adjs[b].push_back(c);
adjs[c].push_back(b);
}
if(b!=d){
adjs[b].push_back(d);
adjs[d].push_back(b);
}
it=curs.erase(it);
}
curs.insert({x1,y1});
curs.insert({x2,y1});
}
if(t==REM){
auto[x1,y1,x2,y2]=rcts[i];
if(curs.count(x1)){
pair<I,I>a={x1,curs[x1]},b={x1,y2};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(curs.count(x2)){
pair<I,I>a={x2,curs[x2]},b={x2,y2};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({x1,y2});
curs.insert({x2,y2});
}
}
curs.clear();
ques.push_back({0,LOC,-1});
ques.push_back({0,LDC,-1});
ques.push_back({x,DES,-1});
ques.push_back({x,DLC,-1});
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
ques.push_back({x2,ADD,i});
ques.push_back({x1,REM,i});
}
sort(ques.begin(),ques.end());
while(ques.size()){
auto[cur,t,i]=ques.back();ques.pop_back();
if(t==LOC){
if(curs.count(0)){
pair<I,I>a={curs[0],0},b={0,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,0});
}
if(t==DES){
if(curs.count(y)){
pair<I,I>a={curs[y],y},b={x,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({y,x});
}
if(t==LDC){
if(curs.count(y)){
pair<I,I>a={curs[y],y},b={0,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({y,0});
}
if(t==DLC){
if(curs.count(0)){
pair<I,I>a={curs[0],0},b={x,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,x});
}
if(t==ADD){
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(y1);
auto upp=curs.upper_bound(y2);
for(auto it=low;it!=upp;){
auto[y,x]=*it;
pair<I,I>a={x,y},b={x2,y};
pair<I,I>c={x2,y1},d={x2,y2};
if(a!=b){
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(b!=c){
adjs[b].push_back(c);
adjs[c].push_back(b);
}
if(b!=d){
adjs[b].push_back(d);
adjs[d].push_back(b);
}
it=curs.erase(it);
}
curs.insert({y1,x2});
curs.insert({y2,x2});
}
if(t==REM){
auto[x1,y1,x2,y2]=rcts[i];
if(curs.count(y1)){
pair<I,I>a={curs[y1],y1},b={x1,y1};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(curs.count(y2)){
pair<I,I>a={curs[y2],y2},b={x1,y2};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({y1,x1});
curs.insert({y2,x1});
}
}
curs.clear();
ques.push_back({0,LOC,-1});
ques.push_back({y,LDC,-1});
ques.push_back({0,DLC,-1});
ques.push_back({y,DES,-1});
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
ques.push_back({y2,ADD,i});
ques.push_back({y1,REM,i});
}
sort(ques.begin(),ques.end());
while(ques.size()){
auto[cur,t,i]=ques.back();ques.pop_back();
if(t==LOC){
if(curs.count(0)){
pair<I,I>a={0,curs[0]},b={0,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,0});
}
if(t==DES){
if(curs.count(x)){
pair<I,I>a={x,curs[x]},b={x,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({x,y});
}
if(t==LDC){
if(curs.count(0)){
pair<I,I>a={0,curs[0]},b={0,y};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({0,y});
}
if(t==DLC){
if(curs.count(x)){
pair<I,I>a={x,curs[x]},b={x,0};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({x,0});
}
if(t==ADD){
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(x1);
auto upp=curs.upper_bound(x2);
for(auto it=low;it!=upp;){
auto[x,y]=*it;
pair<I,I>a={x,y},b={x,y2};
pair<I,I>c={x1,y2},d={x2,y2};
if(a!=b){
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(b!=c){
adjs[b].push_back(c);
adjs[c].push_back(b);
}
if(b!=d){
adjs[b].push_back(d);
adjs[d].push_back(b);
}
it=curs.erase(it);
}
curs.insert({x1,y2});
curs.insert({x2,y2});
}
if(t==REM){
auto[x1,y1,x2,y2]=rcts[i];
if(curs.count(x1)){
pair<I,I>a={x1,curs[x1]},b={x1,y1};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
if(curs.count(x2)){
pair<I,I>a={x2,curs[x2]},b={x2,y1};
adjs[a].push_back(b);
adjs[b].push_back(a);
}
curs.insert({x1,y1});
curs.insert({x2,y1});
}
}
curs.clear();
add({0,0},{0,{-1,-1}});
while(djks.size()){
auto[dis,a]=djks.top();djks.pop();
if((dis=-dis)!=diss[a].first)continue;
sort(adjs[a].begin(),adjs[a].end());
adjs[a].erase(unique(adjs[a].begin(),adjs[a].end()),adjs[a].end());
for(auto b:adjs[a]){
I d=dis+abs(a.first-b.first)+abs(a.second-b.second);
add(b,{d,a});
}
}
for(pair<I,I>a={x,y};;){
auto[dis,b]=diss[a];
if(b==pair<I,I>{-1,-1})break;
ress.push_back({a.first-b.first,a.second-b.second});
a=b;
}
reverse(ress.begin(),ress.end());
printf("%lli\n",diss[{x,y}].first);
printf("%i\n",ress.size());
for(auto[x,y]:ress)printf("%i %i\n",x,y);
}
Compilation message
walk.cpp: In function 'I main()':
walk.cpp:393:12: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
393 | printf("%i\n",ress.size());
| ~^ ~~~~~~~~~~~
| | |
| int std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
| %li
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
468 KB |
Output is correct |
| 4 |
Correct |
34 ms |
2668 KB |
Output is correct |
| 5 |
Execution timed out |
1095 ms |
109392 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1087 ms |
68048 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1080 ms |
86844 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1081 ms |
102396 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1096 ms |
102636 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1085 ms |
102160 KB |
Time limit exceeded |
