| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 711225 |
2023-03-16T10:34:21 Z |
EthanKim8683 |
Walk (CEOI06_walk) |
C++17 |
|
85 ms |
14980 KB |
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const I X=1e6;
const I Y=1e6;
const Lli MAX=1e18;
tuple<I,I,I,I>rcts[N];
vector<pair<I,I>>ques;
map<I,I>curs;
pair<Lli,I>trns[2][1+2*N];
pair<I,I>pnts[2][1+2*N];
vector<pair<I,I>>ress;
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,y1,x2,y2};
}
tuple<Lli,I,I>res={MAX,-1,-1};
if(x!=0){
I low=-Y,upp=Y;
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
if(x>0){
pnts[0][i*2+1]={x1-1,y1-1};
pnts[0][i*2+2]={x1-1,y2+1};
if(x1<x)ques.push_back({-(x1-1),i});
}
if(x<0){
pnts[0][i*2+1]={x2+1,y1-1};
pnts[0][i*2+2]={x2+1,y2+1};
if(x2>x)ques.push_back({x2+1,i});
}
if(x1<=x&&x<=x2){
if(y1>y)upp=min(upp,y1-1);
if(y2<y)low=max(low,y2+1);
}
}
sort(ques.begin(),ques.end());
fill_n(trns[0],1+2*n,pair<Lli,I>{MAX,-1});
trns[0][0]={0,0};
curs.insert({0,0});
while(ques.size()){
auto[t,i]=ques.back();ques.pop_back(),t=-t;
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(y1-1);
auto upp=curs.upper_bound(y2+1);
I k=i*2+1,l=i*2+2;
for(auto it=low;it!=upp;it=curs.erase(it)){
auto[y3,j]=*it;I x3=pnts[0][j].first;
Lli dis=trns[0][j].first+abs(x3-t);
trns[0][k]=min(trns[0][k],{abs(y3-(y1-1))+dis,j});
trns[0][l]=min(trns[0][l],{abs(y3-(y2+1))+dis,j});
}
if(trns[0][k].first!=MAX)curs.insert({y1-1,k});
if(trns[0][l].first!=MAX)curs.insert({y2+1,l});
}
for(auto[y1,i]:curs)if(low<=y1&&y1<=upp){
I x1=pnts[0][i].first;
Lli dis=trns[0][i].first+abs(x-x1)+abs(y-y1);
res=min(res,{dis,0,i});
}
curs.clear();
}
if(y!=0){
I low=-X,upp=X;
for(I i=0;i<n;i++){
auto[x1,y1,x2,y2]=rcts[i];
if(y>0){
pnts[1][i*2+1]={x1-1,y1-1};
pnts[1][i*2+2]={x2+1,y1-1};
if(y1<y)ques.push_back({-(y1-1),i});
}
if(y<0){
pnts[1][i*2+1]={x1-1,y2+1};
pnts[1][i*2+2]={x2+1,y2+1};
if(y2>y)ques.push_back({y2+1,i});
}
if(y1<=y&&y<=y2){
if(x1>x)upp=min(upp,x1-1);
if(x2<x)low=max(low,x2+1);
}
}
sort(ques.begin(),ques.end());
fill_n(trns[1],1+2*n,pair<Lli,I>{MAX,-1});
trns[1][0]={0,0};
curs.insert({0,0});
while(ques.size()){
auto[t,i]=ques.back();ques.pop_back(),t=-t;
auto[x1,y1,x2,y2]=rcts[i];
auto low=curs.lower_bound(x1-1);
auto upp=curs.upper_bound(x2+1);
I k=i*2+1,l=i*2+2;
for(auto it=low;it!=upp;it=curs.erase(it)){
auto[x3,j]=*it;I y3=pnts[1][j].second;
Lli dis=trns[1][j].first+abs(y3-t);
trns[1][k]=min(trns[1][k],{abs(x3-(x1-1))+dis,j});
trns[1][l]=min(trns[1][l],{abs(x3-(x2+1))+dis,j});
}
if(trns[1][k].first!=MAX)curs.insert({x1-1,k});
if(trns[1][l].first!=MAX)curs.insert({x2+1,l});
}
for(auto[x1,i]:curs)if(low<=x1&&x1<=upp){
I y1=pnts[1][i].second;
Lli dis=trns[1][i].first+abs(x-x1)+abs(y-y1);
res=min(res,{dis,1,i});
}
curs.clear();
}
auto[dis,t,i]=res;
if(t==0){
I x1=x,y1=y;
while(i!=0){
auto[x2,y2]=pnts[0][i];
if(y1!=y2)ress.push_back({0,y1-y2});
if(x1!=x2)ress.push_back({x1-x2,0});
x1=x2,y1=y2,i=trns[0][i].second;
}
if(y1!=0)ress.push_back({0,y1-0});
if(x1!=0)ress.push_back({x1-0,0});
}
if(t==1){
I x1=x,y1=y;
while(i!=0){
auto[x2,y2]=pnts[1][i];
if(x1!=x2)ress.push_back({x1-x2,0});
if(y1!=y2)ress.push_back({0,y1-y2});
x1=x2,y1=y2,i=trns[1][i].second;
}
if(x1!=0)ress.push_back({x1-0,0});
if(y1!=0)ress.push_back({0,y1-0});
}
reverse(ress.begin(),ress.end());
printf("%lli\n",dis);
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:141: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=]
141 | 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 |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
484 KB |
Output is correct |
| 5 |
Correct |
76 ms |
13032 KB |
Output is correct |
| 6 |
Correct |
20 ms |
4624 KB |
Output is correct |
| 7 |
Incorrect |
31 ms |
7456 KB |
Found length 1000000000000000000, official output says 109253. |
| 8 |
Incorrect |
63 ms |
14076 KB |
Found length 1000000000000000000, official output says 16349. |
| 9 |
Correct |
76 ms |
14788 KB |
Output is correct |
| 10 |
Correct |
85 ms |
14980 KB |
Output is correct |
