oj.uz

답안 #209691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209691 2020-03-15T08:45:35 Z jwvg0425 전압 (JOI14_voltage) C++17
45 / 100
 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);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 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

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 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 -