oj.uz

Submission #209706

# Submission time Handle Problem Language Result Execution time Memory
209706 2020-03-15T10:29:09 Z jwvg0425 전압 (JOI14_voltage) C++17
100 / 100
 930 ms 72940 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;
    }
}

set<ii> isOdd;
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.find({ now, e }) != isOdd.end())
                    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 (int i = 0; i < oddCycle.size(); i++)
    {
        int x = oddCycle[i];
        int y = oddCycle[(i + 1) % oddCycle.size()];
        isOdd.emplace(x, y);
        isOdd.emplace(y, x);
    }

    coloring(n);

    // odd cycle 제외한 위치에서 문제 있는지 확인
    for (int i = 1; i <= n; i++)
    {
        for (auto& e : edge[i])
        {
            if (isOdd.find({ i,e }) != isOdd.end())
                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)
    {
        if (oddComp[pi].size() == 1)
            continue;

        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))
                swap(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:208:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < oddCycle.size(); i++)
                     ~~^~~~~~~~~~~~~~~~~
voltage.cpp:239:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < oddCycle.size(); i++)
                     ~~^~~~~~~~~~~~~~~~~
voltage.cpp:256:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < oddComp[pi].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~~~~
voltage.cpp:282:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < oddCycle.size(); i++)
                     ~~^~~~~~~~~~~~~~~~~
voltage.cpp:286: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15480 KB Output is correct
2 Correct 14 ms 15224 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Correct 15 ms 15352 KB Output is correct
5 Correct 16 ms 15480 KB Output is correct
6 Correct 17 ms 16632 KB Output is correct
7 Correct 17 ms 16504 KB Output is correct
8 Correct 16 ms 16248 KB Output is correct
9 Correct 16 ms 16248 KB Output is correct
10 Correct 15 ms 15608 KB Output is correct
11 Correct 16 ms 16376 KB Output is correct
12 Correct 16 ms 16376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 32624 KB Output is correct
2 Correct 367 ms 39032 KB Output is correct
3 Correct 288 ms 35144 KB Output is correct
4 Correct 407 ms 42732 KB Output is correct
5 Correct 40 ms 19192 KB Output is correct
6 Correct 321 ms 36088 KB Output is correct
7 Correct 723 ms 69864 KB Output is correct
8 Correct 305 ms 43900 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 32624 KB Output is correct
2 Correct 123 ms 43944 KB Output is correct
3 Correct 126 ms 43760 KB Output is correct
4 Correct 15 ms 15996 KB Output is correct
5 Correct 397 ms 45776 KB Output is correct
6 Correct 327 ms 32376 KB Output is correct
7 Correct 346 ms 37624 KB Output is correct
8 Correct 417 ms 46796 KB Output is correct
9 Correct 581 ms 55936 KB Output is correct
10 Correct 314 ms 37112 KB Output is correct
11 Correct 353 ms 34700 KB Output is correct
12 Correct 397 ms 38408 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 33260 KB Output is correct
2 Correct 187 ms 44144 KB Output is correct
3 Correct 16 ms 16376 KB Output is correct
4 Correct 553 ms 52512 KB Output is correct
5 Correct 662 ms 61008 KB Output is correct
6 Correct 561 ms 53276 KB Output is correct
7 Correct 654 ms 51960 KB Output is correct
8 Correct 860 ms 67408 KB Output is correct
9 Correct 749 ms 57476 KB Output is correct
10 Correct 646 ms 55416 KB Output is correct
11 Correct 702 ms 52572 KB Output is correct
12 Correct 791 ms 62596 KB Output is correct
13 Correct 490 ms 41840 KB Output is correct
14 Correct 930 ms 72940 KB Output is correct
15 Correct 714 ms 61860 KB Output is correct
16 Correct 723 ms 60492 KB Output is correct
17 Correct 610 ms 51704 KB Output is correct
18 Correct 489 ms 44776 KB Output is correct