제출 #791078

#제출 시각아이디문제언어결과실행 시간메모리
791078dooweyParking (CEOI22_parking)C++17
100 / 100
219 ms53080 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = (int)2e5 + 10; const int M = (int)1e6 + 10; set<int> empt; int A[N][2]; bool vis[N][2]; vector<pii> pos[N]; struct elem{ int idx; int up_pair; int cycle; bool operator< (const elem &ee) const { if(cycle == ee.cycle) return up_pair > ee.up_pair; else return cycle > ee.cycle; } }; struct chain{ vector<pii> C; int up_pair; bool cycle; }; chain E[M]; int id; vector<pii> trav; int upper; void dfs(int u, int v){ vis[u][v]=true; trav.push_back(mp(u,v)); if(A[u][(v^1)] != 0 && !vis[u][(v^1)]){ dfs(u,(v^1)); return; } for(auto x : pos[A[u][v]]){ if(!vis[x.fi][x.se]){ if((v & x.se) == 1) upper ++ ; // upper pair dfs(x.fi,x.se); return; } } } vector<pii> oper; priority_queue<elem> ee; void solve_weak_chain(vector<pii> zz){ if(zz.empty()) return; int l = 0; int r = (int)zz.size() - 1; while(l < r){ if(zz[l].se == 0 && zz[l + 1].se == 1){ oper.push_back(mp(zz[l + 1].fi, zz[l].fi)); // zz[l + 1].fi -> zz[l].fi l += 2 ; } else if(zz[r].se == 0 && zz[r - 1].se == 1){ oper.push_back(mp(zz[r - 1].fi, zz[r].fi)); r -= 2 ; } else{ break; } } oper.push_back(mp(zz[l].fi, zz[r].fi)); empt.insert(zz[l].fi); } int fin(){ if(empt.empty()) { cout << "-1\n"; exit(0); return -1; } int id = *empt.begin(); empt.erase(empt.begin()); return id; } void solve_chain(int id){ vector<pii> pp; int chk; for(int i = 0 ; i < E[id].C.size(); i ++ ){ if(i + 1 < E[id].C.size() && E[id].C[i].se == 1 && E[id].C[i + 1].se == 1){ chk = fin(); oper.push_back(mp(E[id].C[i].fi, chk)); oper.push_back(mp(E[id].C[i + 1].fi, chk)); solve_weak_chain(pp); pp.clear(); i++; continue; } else{ pp.push_back(E[id].C[i]); } } solve_weak_chain(pp); } void solve_cycle(int id){ int j; int chk; vector<pii> tt; for(int i = 0 ; i < E[id].C.size(); i ++ ){ j = (i + 1) % E[id].C.size(); if(E[id].C[i].se == 1 && E[id].C[j].se == 1){ chk = fin(); oper.push_back(mp(E[id].C[i].fi, chk)); oper.push_back(mp(E[id].C[j].fi, chk)); for(int add = 1; add + 1 < E[id].C.size(); add ++ ){ tt.push_back(E[id].C[(j + add) % E[id].C.size()]); } break; } } pii nw; if(tt.empty()){ for(int i = 0 ; i < E[id].C.size(); i ++ ){ j = (i + 1) % E[id].C.size(); if(E[id].C[i].se == 1 && E[id].C[j].se == 0){ chk = fin(); oper.push_back(mp(E[id].C[i].fi, chk)); nw = mp(chk, 0); tt.push_back(nw); for(int g = 0; g + 1 < E[id].C.size(); g ++ ){ tt.push_back(E[id].C[(j + g) % E[id].C.size()]); } break; } } } int tp = 0; for(int i = 0 ; i + 1 < tt.size(); i ++ ){ if((tt[i].se & tt[i + 1].se) == 1){ tp ++ ; } } E[id] = {tt, tp, false}; ee.push({id, tp, false}); id ++ ; } void solve(int id){ if(E[id].cycle) solve_cycle(id); else solve_chain(id); } int main(){ fastIO; int n, m; cin >> n >> m; int x, y; for(int i = 1; i <= m; i ++ ){ cin >> x >> y; if(x == 0 && y == 0) empt.insert(i); else{ if(x==y) continue; // we dont look at et A[i][0] = x; A[i][1] = y; for(int j = 0 ; j < 2; j ++ ){ if(A[i][j] != 0)pos[A[i][j]].push_back(mp(i,j)); } } } for(int i = 1; i <= m; i ++ ){ if(A[i][0] != 0 && A[i][1] == 0 && !vis[i][0]){ // NO cycle trav.clear(); upper = 0; dfs(i,0); E[id] = {trav, upper, false}; ee.push({id, upper, false}); id ++ ; } } for(int i = 1; i <= m; i ++ ){ if(A[i][0] != 0 && !vis[i][0]){ // cycle? trav.clear(); upper = 0; dfs(i,0); E[id] = {trav, upper, true}; ee.push({id, upper, true}); id ++ ; } } elem U; while(!ee.empty()){ U = ee.top(); ee.pop(); solve(U.idx); } cout << oper.size() << "\n"; for(auto xx : oper){ cout << xx.fi << " " << xx.se << "\n"; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void solve_chain(int)':
Main.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0 ; i < E[id].C.size(); i ++ ){
      |                  ~~^~~~~~~~~~~~~~~~
Main.cpp:103:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   if(i + 1 < E[id].C.size() && E[id].C[i].se == 1 && E[id].C[i + 1].se == 1){
      |      ~~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void solve_cycle(int)':
Main.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i = 0 ; i < E[id].C.size(); i ++ ){
      |                  ~~^~~~~~~~~~~~~~~~
Main.cpp:129:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |    for(int add = 1; add + 1 < E[id].C.size(); add ++ ){
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:137:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int i = 0 ; i < E[id].C.size(); i ++ ){
      |                   ~~^~~~~~~~~~~~~~~~
Main.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for(int g = 0; g + 1 < E[id].C.size(); g ++ ){
      |                    ~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:152:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int i = 0 ; i + 1 < tt.size(); i ++ ){
      |                  ~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...