oj.uz

Submission #209688

# Submission time Handle Problem Language Result Execution time Memory
209688 2020-03-15T08:14:20 Z jwvg0425 전압 (JOI14_voltage) C++17
45 / 100
 532 ms 61544 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++)
    {
        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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15480 KB Output is correct
2 Correct 14 ms 15228 KB Output is correct
3 Incorrect 14 ms 15992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 33652 KB Output is correct
2 Correct 361 ms 39928 KB Output is correct
3 Correct 270 ms 36080 KB Output is correct
4 Correct 390 ms 43632 KB Output is correct
5 Correct 34 ms 18808 KB Output is correct
6 Correct 323 ms 36984 KB Output is correct
7 Correct 532 ms 61544 KB Output is correct
8 Correct 296 ms 44788 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 33264 KB Output is correct
2 Correct 122 ms 44784 KB Output is correct
3 Correct 121 ms 44792 KB Output is correct
4 Correct 14 ms 15992 KB Output is correct
5 Correct 312 ms 42704 KB Output is correct
6 Correct 312 ms 33272 KB Output is correct
7 Correct 334 ms 38520 KB Output is correct
8 Correct 343 ms 45520 KB Output is correct
9 Correct 449 ms 51200 KB Output is correct
10 Correct 319 ms 38008 KB Output is correct
11 Correct 342 ms 35600 KB Output is correct
12 Correct 356 ms 38536 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 34412 KB Output is correct
2 Correct 178 ms 45940 KB Output is correct
3 Correct 15 ms 16376 KB Output is correct
4 Incorrect 441 ms 49056 KB Output isn't correct
5 Halted 0 ms 0 KB -