이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Arayi
#include <bits/stdc++.h>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;
lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = {'a', 'e', 'i', 'o', 'u'};
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0};
char dc[] = {'R', 'D', 'L', 'U'};
const int N = 5e5 + 20;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const ld e = 1e-13;
const int T = 128;
lli bp(lli a, lli b = mod - 2LL)
{
lli ret = 1;
while (b)
{
if (b & 1)
ret *= a, ret %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ret;
}
ostream &operator<<(ostream &c, pir a)
{
c << a.fr << " " << a.sc;
return c;
}
template <class T>
void maxi(T &a, T b)
{
a = max(a, b);
}
template <class T>
void mini(T &a, T b)
{
a = min(a, b);
}
int n, m;
vii az, ind[N], g[N], g1[N];
bool col[N];
int a[N][2], t[N];
vii tp[3];
vector<pir> pat;
vii gg[N], gg1[N];
priority_queue<pair<int, int>> q;
void dfs(int v, int x1)
{
if (t[v] == 1)
gg1[x1].ad(v), gg[v].ad(x1);
for (auto p : g1[v])
dfs(p, x1);
}
vii sm;
void dfs1(int v)
{
bool bl = 0;
for (auto p : g[v])
{
if(!col[p])
{
dfs1(p);
bl = 1;
}
}
if(!bl) sm.ad(v);
}
void han(int i1)
{
if (col[i1])
return;
if (t[i1] == 3)
{
if (az.empty())
{
cout << -1 << endl;
exit(0);
}
pat.ad(MP(ind[i1][0], az.back()));
pat.ad(MP(ind[i1][1], az.back()));
az.pop_back();
col[i1] = 1;
for (auto p : gg1[i1])
{
for (int i = 0; i < gg[p].size(); i++)
{
if (gg[p][i] == i1)
{
swap(gg[p][i], gg[p].back());
gg[p].pop_back();
break;
}
}
q.push(MP(-gg[p].size(), p));
}
for (auto p : g1[i1])
han(p);
}
else if (t[i1] == 2)
{
col[i1] = 1;
pat.ad(MP(ind[i1][1], ind[i1][0]));
for (auto p : g1[i1])
han(p);
}
else
{
if (gg[i1].empty())
{
sm.clear();
dfs1(i1);
if (sm[0] == i1)
{
pat.ad(MP(ind[i1][1], ind[i1][0]));
az.ad(ind[i1][1]);
col[i1] = 1;
}
else
for(auto p : sm) han(p);
}
}
}
int main()
{
fastio;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
::a[i][0] = a, ::a[i][1] = b;
if (a == 0)
az.ad(i);
else
ind[a].ad(i), ind[b].ad(i);
if (a == b)
col[a] = 1;
}
for (int i = 1; i <= n; i++)
{
if (col[i])
continue;
int i1 = ind[i][0], i2 = ind[i][1];
if (a[i1][0] == i && a[i2][0] == i)
{
if (a[i1][1])
g[i].ad(a[i1][1]);
if (a[i2][1])
g[i].ad(a[i2][1]);
tp[0].ad(i);
t[i] = 1;
}
if (a[i1][1] == i && a[i2][0] == i)
swap(ind[i][0], ind[i][1]), swap(i1, i2);
if (a[i1][0] == i && a[i2][1] == i)
{
if (a[i1][1])
g[i].ad(a[i1][1]);
g1[i].ad(a[i2][0]);
tp[1].ad(i);
t[i] = 2;
}
if (a[i1][1] == i && a[i2][1] == i)
{
g1[i].ad(a[i1][0]);
g1[i].ad(a[i2][0]);
tp[2].ad(i);
t[i] = 3;
}
/*cout << i << "-";
for(auto p : g[i]) cout << p << " ";
cout << endl;*/
}
for (auto p : tp[2])
dfs(p, p);
/*for(auto p : tp[0])
{
cout << p << "-";
for(auto p1 : gg[p]) cout << p1 << " ";
cout << endl;
}
for(auto p : tp[2])
{
cout << p << "-";
for(auto p1 : gg1[p]) cout << p1 << " ";
cout << endl;
}*/
for (auto p : tp[0])
q.push(MP(-gg[p].size(), p));
while (!q.empty())
{
auto p = q.top();
q.pop();
if (col[p.sc])
continue;
sm.clear();
dfs1(p.sc);
for (auto p1 : sm)
han(p1);
}
for (int i = 1; i <= n; i++)
{
if (!col[i] && t[i] == 3)
han(i);
}
for (int i = 1; i <= n; i++)
{
if (!col[i] && t[i] == 2)
{
if (az.empty())
{
cout << -1 << endl;
exit(0);
}
pat.ad(MP(ind[i][1], az.back()));
ind[i][1] = az.back();
han(g1[i][0]);
}
}
cout << pat.size() << endl;
for (auto p : pat)
cout << p.fr << " " << p.sc << "\n";
return 0;
}
/*
__
*(><)*
\/ /
||/
--||
||
/\
/ \
/ \
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void han(int)':
Main.cpp:124:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < gg[p].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... |