Submission #711004

#	Time	Username	Problem	Language	Result	Execution time	Memory
711004		EthanKim8683	Walk (CEOI06_walk)	C++17	40 / 100	1077 ms	131072 KiB

walk

#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>,set<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].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={x,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({y,x});
    }
    if(t==LDC){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={0,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({y,0});
    }
    if(t==DLC){
      if(curs.count(0)){
        pair<I,I>a={curs[0],0},b={x,0};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
          adjs[b].insert(a);
        }
        if(b!=c){
          adjs[b].insert(c);
          adjs[c].insert(b);
        }
        if(b!=d){
          adjs[b].insert(d);
          adjs[d].insert(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].insert(b);
        adjs[b].insert(a);
      }
      if(curs.count(y2)){
        pair<I,I>a={curs[y2],y2},b={x2,y2};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({x,y});
    }
    if(t==LDC){
      if(curs.count(0)){
        pair<I,I>a={0,curs[0]},b={0,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({0,y});
    }
    if(t==DLC){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,0};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
          adjs[b].insert(a);
        }
        if(b!=c){
          adjs[b].insert(c);
          adjs[c].insert(b);
        }
        if(b!=d){
          adjs[b].insert(d);
          adjs[d].insert(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].insert(b);
        adjs[b].insert(a);
      }
      if(curs.count(x2)){
        pair<I,I>a={x2,curs[x2]},b={x2,y2};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={x,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({y,x});
    }
    if(t==LDC){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={0,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({y,0});
    }
    if(t==DLC){
      if(curs.count(0)){
        pair<I,I>a={curs[0],0},b={x,0};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
          adjs[b].insert(a);
        }
        if(b!=c){
          adjs[b].insert(c);
          adjs[c].insert(b);
        }
        if(b!=d){
          adjs[b].insert(d);
          adjs[d].insert(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].insert(b);
        adjs[b].insert(a);
      }
      if(curs.count(y2)){
        pair<I,I>a={curs[y2],y2},b={x1,y2};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({x,y});
    }
    if(t==LDC){
      if(curs.count(0)){
        pair<I,I>a={0,curs[0]},b={0,y};
        adjs[a].insert(b);
        adjs[b].insert(a);
      }
      curs.insert({0,y});
    }
    if(t==DLC){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,0};
        adjs[a].insert(b);
        adjs[b].insert(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].insert(b);
          adjs[b].insert(a);
        }
        if(b!=c){
          adjs[b].insert(c);
          adjs[c].insert(b);
        }
        if(b!=d){
          adjs[b].insert(d);
          adjs[d].insert(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].insert(b);
        adjs[b].insert(a);
      }
      if(curs.count(x2)){
        pair<I,I>a={x2,curs[x2]},b={x2,y1};
        adjs[a].insert(b);
        adjs[b].insert(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;
    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 (stderr)

walk.cpp: In function 'I main()':
walk.cpp:391: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=]
  391 |   printf("%i\n",ress.size());
      |           ~^    ~~~~~~~~~~~
      |            |             |
      |            int           std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |           %li

• Subtask 1: 40 / 100