oj.uz

Submission #209704

# Submission time Handle Problem Language Result Execution time Memory
209704 2020-03-15T10:04:19 Z jwvg0425 전압 (JOI14_voltage) C++17
45 / 100
 623 ms 61412 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++)
        {
            for (int j = 0; j < oddComp[pi].size(); j++)
            {
                if (i == j)
                    continue;

                auto a = oddComp[pi][i];
                auto b = oddComp[pi][j];
                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:253:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < oddComp[pi].size(); j++)
                             ~~^~~~~~~~~~~~~~~~~~~~
voltage.cpp:285:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < oddCycle.size(); i++)
                     ~~^~~~~~~~~~~~~~~~~
voltage.cpp:289: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 16 ms 15480 KB Output is correct
2 Correct 14 ms 15096 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Correct 16 ms 15352 KB Output is correct
5 Correct 16 ms 15480 KB Output is correct
6 Incorrect 18 ms 16508 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 33520 KB Output is correct
2 Correct 353 ms 39928 KB Output is correct
3 Correct 264 ms 36040 KB Output is correct
4 Correct 395 ms 43632 KB Output is correct
5 Correct 35 ms 18936 KB Output is correct
6 Correct 324 ms 36984 KB Output is correct
7 Correct 609 ms 61412 KB Output is correct
8 Correct 299 ms 44784 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 33136 KB Output is correct
2 Correct 124 ms 44788 KB Output is correct
3 Correct 124 ms 44764 KB Output is correct
4 Correct 14 ms 15992 KB Output is correct
5 Correct 329 ms 42680 KB Output is correct
6 Correct 318 ms 33272 KB Output is correct
7 Correct 355 ms 38520 KB Output is correct
8 Correct 384 ms 45452 KB Output is correct
9 Correct 492 ms 51072 KB Output is correct
10 Correct 319 ms 38008 KB Output is correct
11 Correct 344 ms 35604 KB Output is correct
12 Correct 367 ms 38476 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 34028 KB Output is correct
2 Correct 180 ms 44916 KB Output is correct
3 Correct 15 ms 16376 KB Output is correct
4 Incorrect 623 ms 49056 KB Output isn't correct
5 Halted 0 ms 0 KB -