답안 #710995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710995 2023-03-16T06:58:22 Z EthanKim8683 Walk (CEOI06_walk) C++17
40 / 100
1000 ms 125260 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<pair<I,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};
        I dis=abs(0-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={x,y};
        I dis=abs(x-curs[y]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({y,x});
    }
    if(t==LDC){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={0,y};
        I dis=abs(0-curs[y]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({y,0});
    }
    if(t==DLC){
      if(curs.count(0)){
        pair<I,I>a={curs[0],0},b={x,0};
        I dis=abs(x-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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){
          I dis=abs(x-x1);
          adjs[a].push_back({b,dis});
          adjs[b].push_back({a,dis});
        }
        if(b!=c){
          I dis=abs(y-y1);
          adjs[b].push_back({c,dis});
          adjs[c].push_back({b,dis});
        }
        if(b!=d){
          I dis=abs(y-y2);
          adjs[b].push_back({d,dis});
          adjs[d].push_back({b,dis});
        }
        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};
        I dis=abs(x2-curs[y1]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      if(curs.count(y2)){
        pair<I,I>a={curs[y2],y2},b={x2,y2};
        I dis=abs(x2-curs[y2]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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};
        I dis=abs(0-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,y};
        I dis=abs(y-curs[x]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({x,y});
    }
    if(t==LDC){
      if(curs.count(0)){
        pair<I,I>a={0,curs[0]},b={0,y};
        I dis=abs(y-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({0,y});
    }
    if(t==DLC){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,0};
        I dis=abs(0-curs[x]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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){
          I dis=abs(y-y1);
          adjs[a].push_back({b,dis});
          adjs[b].push_back({a,dis});
        }
        if(b!=c){
          I dis=abs(x-x1);
          adjs[b].push_back({c,dis});
          adjs[c].push_back({b,dis});
        }
        if(b!=d){
          I dis=abs(x-x2);
          adjs[b].push_back({d,dis});
          adjs[d].push_back({b,dis});
        }
        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};
        I dis=abs(y2-curs[x1]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      if(curs.count(x2)){
        pair<I,I>a={x2,curs[x2]},b={x2,y2};
        I dis=abs(y2-curs[x2]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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};
        I dis=abs(0-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={x,y};
        I dis=abs(x-curs[y]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({y,x});
    }
    if(t==LDC){
      if(curs.count(y)){
        pair<I,I>a={curs[y],y},b={0,y};
        I dis=abs(0-curs[y]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({y,0});
    }
    if(t==DLC){
      if(curs.count(0)){
        pair<I,I>a={curs[0],0},b={x,0};
        I dis=abs(x-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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){
          I dis=abs(x-x2);
          adjs[a].push_back({b,dis});
          adjs[b].push_back({a,dis});
        }
        if(b!=c){
          I dis=abs(y-y1);
          adjs[b].push_back({c,dis});
          adjs[c].push_back({b,dis});
        }
        if(b!=d){
          I dis=abs(y-y2);
          adjs[b].push_back({d,dis});
          adjs[d].push_back({b,dis});
        }
        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};
        I dis=abs(x1-curs[y1]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      if(curs.count(y2)){
        pair<I,I>a={curs[y2],y2},b={x1,y2};
        I dis=abs(x1-curs[y2]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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};
        I dis=abs(0-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({0,0});
    }
    if(t==DES){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,y};
        I dis=abs(y-curs[x]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({x,y});
    }
    if(t==LDC){
      if(curs.count(0)){
        pair<I,I>a={0,curs[0]},b={0,y};
        I dis=abs(y-curs[0]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      curs.insert({0,y});
    }
    if(t==DLC){
      if(curs.count(x)){
        pair<I,I>a={x,curs[x]},b={x,0};
        I dis=abs(0-curs[x]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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){
          I dis=abs(y-y2);
          adjs[a].push_back({b,dis});
          adjs[b].push_back({a,dis});
        }
        if(b!=c){
          I dis=abs(x-x1);
          adjs[b].push_back({c,dis});
          adjs[c].push_back({b,dis});
        }
        if(b!=d){
          I dis=abs(x-x2);
          adjs[b].push_back({d,dis});
          adjs[d].push_back({b,dis});
        }
        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};
        I dis=abs(y1-curs[x1]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      if(curs.count(x2)){
        pair<I,I>a={x2,curs[x2]},b={x2,y1};
        I dis=abs(y1-curs[x2]);
        adjs[a].push_back({b,dis});
        adjs[b].push_back({a,dis});
      }
      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,d]:adjs[a])add(b,{dis+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:424: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=]
  424 |   printf("%i\n",ress.size());
      |           ~^    ~~~~~~~~~~~
      |            |             |
      |            int           std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |           %li
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 28 ms 3048 KB Output is correct
5 Execution timed out 1084 ms 125260 KB Time limit exceeded
6 Execution timed out 1076 ms 79528 KB Time limit exceeded
7 Execution timed out 1076 ms 102024 KB Time limit exceeded
8 Execution timed out 1092 ms 111672 KB Time limit exceeded
9 Execution timed out 1082 ms 113972 KB Time limit exceeded
10 Execution timed out 1079 ms 121304 KB Time limit exceeded