이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |