| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 209691 |
2020-03-15T08:45:35 Z |
jwvg0425 |
전압 (JOI14_voltage) |
C++17 |
|
599 ms |
60392 KB |
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> edge[200005];
int bridges = 0;
int par[400005];
int disc[200005];
int d = 0;
map<ii, int> ecount;
int find(int x)
{
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
void merge(int x, int y)
{
x = find(x);
y = find(y);
par[x] = y;
}
int bridge(int here, int par)
{
disc[here] = ++d;
int ret = disc[here];
int child = 0;
for (int there : edge[here])
{
if (there == par)
continue;
if (!disc[there])
{
int df = bridge(there, here);
if (df > disc[here] && ecount[{here, there}] == 1)
bridges++;
ret = min(ret, df);
}
else
{
ret = min(ret, disc[there]);
}
}
return ret;
}
void calcBridge(int n)
{
for (int i = 1; i <= n; i++)
if (!disc[i])
bridge(i, 0);
}
int visited[200005];
vector<int> oddCycle;
vector<pair<int, bool>> oddComp[400005];
bool odd(int root)
{
oddCycle.push_back(root);
for (auto& e : edge[root])
{
if (visited[e] == visited[root])
{
vector<int> trace = { e };
while (oddCycle.back() != e)
{
trace.push_back(oddCycle.back());
oddCycle.pop_back();
}
oddCycle = trace;
return true;
}
if (visited[e] != -1)
continue;
visited[e] = (visited[root] + 1) % 2;
if (odd(e))
return true;
}
oddCycle.pop_back();
return false;
}
void findOddCycle(int n)
{
memset(visited, -1, sizeof(visited));
for (int i = 1; i <= n; i++)
{
if (visited[i] != -1)
continue;
visited[i] = 0;
if (odd(i))
return;
}
}
bool isOdd[200005];
int color[200005];
void coloring(int n)
{
memset(color, -1, sizeof(color));
for (int i = 1; i <= n; i++)
{
if (color[i] != -1)
continue;
vector<int> comp;
queue<int> q;
color[i] = 0;
q.push(i);
while (!q.empty())
{
auto now = q.front();
comp.push_back(now);
q.pop();
for (auto& e : edge[now])
{
if (color[e] != -1 || (isOdd[now] && isOdd[e]))
continue;
color[e] = (color[now] + 1) % 2;
q.push(e);
}
}
for (int j = 0; j < comp.size() - 1; j++)
{
if (color[comp[j]] == color[comp[j + 1]])
{
merge(comp[j], comp[j + 1]);
merge(n + comp[j], n + comp[j + 1]);
}
else
{
merge(comp[j], n + comp[j + 1]);
merge(n + comp[j], comp[j + 1]);
}
}
}
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= 2 * n; i++)
par[i] = i;
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
ecount[{u, v}]++;
ecount[{v, u}]++;
}
calcBridge(n);
findOddCycle(n);
if (oddCycle.empty())
{
printf("%d\n", bridges);
return 0;
}
for (auto& oi : oddCycle)
isOdd[oi] = true;
coloring(n);
// odd cycle 제외한 위치에서 문제 있는지 확인
for (int i = 1; i <= n; i++)
{
if (isOdd[i])
continue;
for (auto & e : edge[i])
{
if (isOdd[e])
continue;
// odd cycle 하나 제거했는데도 여전히 같은 쌍이 나옴 => 불가능
if (find(i) == find(e))
{
printf("0\n");
return 0;
}
}
}
int total = 0;
vector<int> psum(oddCycle.size() + 1);
set<int> ps;
for (int i = 0; i < oddCycle.size(); i++)
{
int x = find(oddCycle[i]);
int y = find(oddCycle[i] + n);
ps.insert(x);
ps.insert(y);
oddComp[x].emplace_back(i, true);
oddComp[y].emplace_back(i, false);
}
for (auto& pi : ps)
{
for (int i = 0; i < oddComp[pi].size(); i++)
{
auto a = oddComp[pi][i];
auto b = oddComp[pi][(i + 1) % oddComp[pi].size()];
int d = b.xx - a.xx;
if (d < 0)
d += oddCycle.size();
if (!(a.yy != b.yy && d % 2 == 0) &&
!(a.yy == b.yy && d % 2 == 1))
continue;
// a ~ b 사이에 하나는 있어야함
total++;
if (a.xx < b.xx)
{
psum[a.xx]++;
psum[b.xx]--;
}
else
{
psum[0]++;
psum[b.xx]--;
psum[a.xx]++;
}
}
}
for (int i = 1; i < oddCycle.size(); i++)
psum[i] += psum[i - 1];
int result = 0;
for (int i = 0; i < oddCycle.size(); i++)
{
int x = oddCycle[i];
int y = oddCycle[(i + 1) % oddCycle.size()];
if (ecount[{x, y}] > 1)
continue;
if (psum[i] == total)
result++;
}
printf("%d\n", result);
return 0;
}
Compilation message
voltage.cpp: In function 'int bridge(int, int)':
voltage.cpp:54:9: warning: unused variable 'child' [-Wunused-variable]
int child = 0;
^~~~~
voltage.cpp: In function 'void coloring(int)':
voltage.cpp:165:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < comp.size() - 1; j++)
~~^~~~~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:237:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < oddCycle.size(); i++)
~~^~~~~~~~~~~~~~~~~
voltage.cpp:251:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < oddComp[pi].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~
voltage.cpp:279:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < oddCycle.size(); i++)
~~^~~~~~~~~~~~~~~~~
voltage.cpp:283:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < oddCycle.size(); i++)
~~^~~~~~~~~~~~~~~~~
voltage.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
15480 KB |
Output is correct |
| 2 |
Correct |
14 ms |
15224 KB |
Output is correct |
| 3 |
Correct |
14 ms |
15992 KB |
Output is correct |
| 4 |
Correct |
15 ms |
15352 KB |
Output is correct |
| 5 |
Correct |
15 ms |
15480 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
16504 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
243 ms |
32496 KB |
Output is correct |
| 2 |
Correct |
359 ms |
38904 KB |
Output is correct |
| 3 |
Correct |
257 ms |
35016 KB |
Output is correct |
| 4 |
Correct |
391 ms |
42480 KB |
Output is correct |
| 5 |
Correct |
36 ms |
18936 KB |
Output is correct |
| 6 |
Correct |
355 ms |
35960 KB |
Output is correct |
| 7 |
Correct |
599 ms |
60392 KB |
Output is correct |
| 8 |
Correct |
294 ms |
43764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
32496 KB |
Output is correct |
| 2 |
Correct |
123 ms |
43728 KB |
Output is correct |
| 3 |
Correct |
122 ms |
43764 KB |
Output is correct |
| 4 |
Correct |
15 ms |
15992 KB |
Output is correct |
| 5 |
Correct |
376 ms |
41856 KB |
Output is correct |
| 6 |
Correct |
314 ms |
32248 KB |
Output is correct |
| 7 |
Correct |
358 ms |
37496 KB |
Output is correct |
| 8 |
Correct |
367 ms |
44492 KB |
Output is correct |
| 9 |
Correct |
539 ms |
50044 KB |
Output is correct |
| 10 |
Correct |
308 ms |
36984 KB |
Output is correct |
| 11 |
Correct |
348 ms |
34580 KB |
Output is correct |
| 12 |
Correct |
352 ms |
37456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
33000 KB |
Output is correct |
| 2 |
Correct |
194 ms |
43764 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16376 KB |
Output is correct |
| 4 |
Incorrect |
478 ms |
47900 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
