Submission #209706

#	Time	Username	Problem	Language	Result	Execution time	Memory
209706		jwvg0425	전압 (JOI14_voltage)	C++17	100 / 100	930 ms	72940 KiB

voltage

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45