제출 #1245082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245082		Joon_Yorigami	Parking (CEOI22_parking)	C++20	100 / 100	684 ms	96812 KiB

Main

/*
                                                                   .:-=++***#***+=:.
                                                       .:-==+**##**%########***#####*=:.
                                                   .-+#%%#*****############**#******#####+=:
                                                .-*%#####********###########*********#######*+-:
                                              :+#######**********########*****+********##########+-.
                                            :+##########**###******##********************###########+:
                                          :+##########*****#*******###**********************###***####*:
                                        .=###########***###*******#***************************#****#####*:
                                       :*#################******************************************######=
                                      -###################***************+****************************#####*:
                                    .=###################******************************************#****#####+.
                                   :*###################*******************************+************#*****#####:
                                  =#############**######*****#*******************++***++++++***************#####=
                                .*###########******####*****#************+++*+**+++***++++++++***#**********#####+
                               -############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####*
                              =############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*.
                            .+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*.
                           .*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*.
               .:-:       .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*.
           .--:++=+.     .**.  ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*:
           :++=====     .**.  -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=:
            .-=++=      =*.   +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+:
                .      .#.   .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+:
                       --    -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-.
         -=+++-.       =     +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=:
       .++====++       =     ####################**##*****###***#+****#=#****  .+*###************+  ##   +***######****##########+--+#%%%%+:
  .---:=+======+:      +.    ##################%#***#*****####****#**#+-####.  .+###***##*******#  .#:   :***########***##%%%####%#=. .:=*%%
 ---==++=======+=      -=   .%#################%****#*****######-#*##*.=%#*.    +=---:::.......:   =:     =**#########***#%%%%%%%%%%%=.   .-
 :-:===========+=      .#.  :%################%%****#*****#####= :-+***#*=.                               .*#########%%#**#*=%%%%%%%%%%=.
  .---=========+=       :*. -#################%%****#*****%#+-.-*#%%%@###*=                                +##########%%%***:+-#%%%#####*:
    .:=++++====+-        =*.=###%############%@%****#*****#. =###%%%@@@+                                   ###########%%%%#*#:  -*########=
        ..:::::-.         +*+###%####%######%%+******#****#=##= -@@@@@@@+                                 =*###########%%%%##+    :*#######+
                           =%##+%####%######%+.******#*****%%#-:+@@@@%-=*                                 +..###########%##%%%*.    -#######
                            %##=#####%###%%#%:=******#*****%*.**##*+=:  .                   -+**####*=:  -  .=###############%%*:    .+#####
                           .%###%########%%%%:.#*****##*****= .+:      .                   :-::.:--=++-  :  .-*##################+:    :####
                           :##.*###########%@# #************+   .:.-==--                                .    +**###+*##############*:   .*##
                           -%- ############%@@-#*###*#=##***#.                                          :.  =*++*#**++*##############*-  .##
                           =#  ############@@@######*#:###*##=                                          :..+*++++***+++++*##############=.+#
                           +:  ###########%@%%%%######.=######                                         .=+#+++++++***+++++****##############
                          .+   *##########%%%%%%######::######=                                        =+++#*+++++++*#+++++******###########
                          +:   =%#%######%%%##%@######:-+######.              .:------==              :*++++**+++++++*#*+++++********#######
                         -*    :%%%%#####%%%##%%%#####***######*             -=--------=:            -*+++++++*++++++++*#**+++*=:=******+==*
                        .*+     +%%%%###%%####%%%#####**+#######=            -........:=:          -++++++++++*#**##***+******++- .-******=.
                        -*=      *%%%%##%%%%%%%#%#####**++#######.           :.........-        .=#%%%######%##########%#+*******.  .-++++*+
                        -*+     .*%%%%#%%#######%#####*++++######*:           .........      :=#%@@%%%%%%#################*++*****=.  .-++++
                        :**.   :###%%%#%%########%####*++++*#######=-:..                  -+#%%%###########################++++****#=.  .-++
                         -*+  .######%%%%#########%###@@@%%%%######+...:----:.         :*%################################%*+++++*+###-   .+
                          :*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+.  .
                            -+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*.  =##+
                             +#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++    -##.
                            =%**********#######%%###############%*#####=...=.        .  :-=-: .###############%#******####%#####+=     +*
                            *#************#############%%#######**+*%####-.-                .-:=##############%*********##%#######=:  .+.
                            *#****************##**######%%%###*:   ::*#####:     -::            .-+####%%%####%*********#%##########*-:
                            =#***********************######%*-        .--:=:.   =. :--:             .-=*###%###*********#######*#######+-
                            .#**************************###=             .:.  ::...   .=.               +***#%##*******#########***#######+:
                             =##**************************:      :-:--.  .. .+.....     +               =******#%#####%##########***#####**#
                              ####**********************+.    . :#########+-=:....      -:              +***********##%%#***######****##****
                              .#%####******************-        *##########*:....... ...:.              #**************##*********###*##****
                               :#%@%%%###*************          =#*******####+....... :-.              *#***************%************#%#****
                              .#**###%%%%%######****#.           =#***********#=....:-.              :*#****************##*************####*
                              *#**#****#####%%%%#####             =#*************+=:       .=-::..:-*#*****************##*****************##
                             -#***#*******######%%%%=               :=*#**********:    ...  ##*##%##*******************#********************
                            .%*****#*********######%.                    ....:-=*-  :++:   =#****##%####*************###********************
:.                          +#*****#**********####%+                            ..-*#***#+=##*******##%%###********####*********************
 .:-:.                     .%#*****#**********#%%%*                  :=+**##########******###********#%%%%%%##****###***********************
     --                    =%#******#*********@#%%-.               :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####*************************
=-.   .=.                  ##*******#********#%#**###*+=-:.:     -######%##%###%####%%%%%##########%####%%%%##%*************####************
====   .=                 :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####***********
 ====   -:                *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####**********
 :+=+.   =               .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######*********
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using sll = set<ll>;
using pll = pair<ll,ll>;

constexpr ll max_n=400010;
ll parent[max_n];
ll sz[max_n];
bool in_cycle[max_n];
ll topcnt[max_n];
ll cnt[max_n];
set<ll> edge[max_n];
vector<pll> moves;
set<ll> available;
bool possible;

ll find(ll x)
{
  if(x==parent[x])
    return x;
  else
    return parent[x] = find(parent[x]);
}

void _union(ll u,ll v)
{
  edge[u].insert(v);
  edge[v].insert(u);
  topcnt[v]+=(u%2)&&(v%2);
  u=find(u);
  v=find(v);
  if(u==v)
    in_cycle[u]=1;
  else
  {
    if(sz[v]>sz[u])
      swap(u,v);
    parent[v]=u;
    sz[u]+=sz[v];
    topcnt[u]+=topcnt[v];
  }
}

void _delete(ll u,ll v)
{
  edge[u].erase(v);
  edge[v].erase(u);
}

ll dfs(ll x)
{
  ll leaf=x;
  stack<ll> stk({x});
  sll seen({x});
  while(!stk.empty())
  {
    ll curr=stk.top();
    stk.pop();
    for(auto neighbour:edge[curr])
    {
      if(seen.find(neighbour)!=seen.end())
        continue;
      seen.insert(neighbour);
      stk.push(neighbour);
      leaf=neighbour;
      break;
    }
  }
  return leaf;
}

void move(ll u,ll v)
{
  moves.push_back({u,v});
  cnt[u]-=1;
  cnt[v]+=1;
  if(cnt[u]==0)
    available.insert(u);
  if(cnt[v]==1)
    available.erase(v);
}

void solve_chain(ll u)
{
  ll curr = dfs(u);
  sll seen({curr});
  vll chain;
  while(curr!=-1)
  {
    chain.push_back(curr);
    ll next = -1;
    for(auto neighbour:edge[curr])
    {
      if(seen.find(neighbour)!=seen.end())
        continue;
      seen.insert(neighbour);
      next=neighbour;
    }
    curr = next;
  }
  ll m=chain.size();
  ll i=0;
  while(i<m)
  {
    ll a=chain[i],b=chain[i+1];
    if(b%2)
    {
      //solvable one move
      move(b/2,a/2);
      i+=2;
      continue;
    }
    ll conflict=-1;
    for(int j=i;j<m-1;j++)
    {
      if(chain[j]%2 && chain[j+1]%2)
      {
        conflict=j;
        break;
      }
    }
    if(conflict==-1)
    {
      //solve all
      for(int j=m-1;j>i+1;j-=2)
        move(chain[j-1]/2,chain[j]/2);
      move(chain[i]/2,chain[i+1]/2);
      break;
    }
    else
    {
      //need 1 available to open chain
      if(available.size()==0)
      {
        possible=false;
        return;
      }
      ll dump=*available.begin();
      move(chain[conflict]/2,dump);
      move(chain[conflict+1]/2,dump);
      for(int j=conflict-1;j>=i;j-=2)
        move(chain[j-1]/2,chain[j]/2);
      i=conflict+2;
    }
  }
}

void solve_cycle(ll u)
{
  if(available.size()==0)
  {
    possible=false;
    return;
  }
  ll curr = u;
  sll seen({curr});
  vll cycle;
  stack<ll> q({curr});
  while(!q.empty())
  {
    curr=q.top();
    q.pop();
    cycle.push_back(curr);
    ll next = -1;
    for(auto neighbour:edge[curr])
    {
      if(seen.find(neighbour)!=seen.end())
        continue;
      seen.insert(neighbour);
      next=neighbour;
      q.push(neighbour);
    }
    curr = next;
  }
  ll m=cycle.size();
  ll start=0;
  for(int i=0;i<m;i++)
  {
    if(cycle[i]%2)
    {
      start=i;
      if(cycle[(i+1)%m]%2)
        break;
    }
  }
  ll a=cycle[start],b=cycle[(start+1)%m];
  ll dump=*available.begin();
  if(b%2)
  {
    //turn to chain
    move(a/2,dump);
    move(b/2,dump);
    _delete(cycle[(start-1+m)%m],cycle[start]);
    _delete(cycle[start%m],cycle[(start+1)%m]);
    _delete(cycle[(start+1)%m],cycle[(start+2)%m]);
    solve_chain(cycle[(start+2)%m]);
  }
  else
  {
    if(a/2!=b/2)
    {
      move(a/2,dump);
      for(int i=2;i<m;i+=2)
        move(cycle[(start-i+m)%m]/2,cycle[(start-i+1+m)%m]/2);
      move(b/2,dump);
    }
    else
    {
      move(a/2,dump);
      for(int i=2;i<m;i+=2)
        move(cycle[(start+i+m)%m]/2,cycle[(start+i-1+m)%m]/2);
      move(cycle[(start-1+m)%m]/2,dump);
    }
  }
}

int main()
{
  possible=true;
  ll n,m;
  cin >> n >> m;
  vector<vll> grid(m,vll(2,0));
  vector<vll> idx(n,vll());
  for(int i=0;i<m;i++)
    for(int j=0;j<2;j++)
      cin >> grid[i][j];
  for(int i=0;i<m;i++)
    for(int j=0;j<2;j++)
      grid[i][j]-=1;
  vector<bool> solved(n,false);
  vll row;
  ll top_car,bot_car;
  for(int i=0;i<m;i++)
  {
    parent[i*2]=i*2;
    sz[i*2]=1;
    parent[i*2+1]=i*2+1;
    sz[i*2+1]=1;
    row=grid[i];
    bot_car=row[0];
    top_car=row[1];
    if(bot_car>=0)
    {
      cnt[i]+=1;
      idx[bot_car].push_back(i*2);
    }
    if(top_car>=0)
    {
      cnt[i]+=1;
      idx[top_car].push_back(i*2+1);
    }
    if(bot_car == -1 && top_car==-1)
      available.insert(i);
  }
  for(int i=0;i<n;i++)
  {
    if(idx[i][0]/2!=idx[i][1]/2)
    {
      _union(idx[i][0],idx[i][1]);
    }
  }
  for(int i=0;i<m;i++)
  {
    if(grid[i][1]>=0 && grid[i][0]!=grid[i][1])
      _union(i*2,i*2+1);
  }
  vector<vll> q;
  for(int i=0;i<m*2;i++)
    if(find(i)==i && sz[i]>1)
      q.push_back({in_cycle[i],topcnt[i],i});
  sort(q.begin(),q.end());
  ll start;
  for(auto row:q)
  {
    start=row[2];
    if(row[0])
      solve_cycle(start);
    else
      solve_chain(start);
    if(!possible)
      break;
  }
  if(!possible)
    cout << "-1" << '\n';
  else
  {
    cout << moves.size() << '\n';
    for(auto row:moves)
      cout << row.first+1 << " " << row.second+1 << '\n';
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15