Submission #209704

#	Time	Username	Problem	Language	Result	Execution time	Memory
209704		jwvg0425	전압 (JOI14_voltage)	C++17	45 / 100	623 ms	61412 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;
    }
}

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