Submission #1195541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195541		raphaelp	Povjerenstvo (COI22_povjerenstvo)	C++20	0 / 100	3097 ms	119748 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void dfs(int x, vector<vector<int>> &AR, vector<int> &ordre, vector<int> &occ)
{
    occ[x] = 1;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (occ[AR[x][i]])
            continue;
        dfs(AR[x][i], AR, ordre, occ);
    }
    ordre.push_back(x);
}
void dfs2(int x, vector<vector<int>> &AR, vector<int> &occ, vector<int> &comp, vector<int> &color, vector<vector<int>> &comps, int c)
{
    color[x] = c;
    occ[x] = 1;
    comp[x] = comps.size() - 1;
    comps.back().push_back(x);
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (occ[AR[x][i]])
            continue;
        dfs2(AR[x][i], AR, occ, comp, color, comps, 0 - c);
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> AR(N), AR2(N);
    vector<int> left(N);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        AR[a].push_back(b);
        AR2[b].push_back(a);
    }
    vector<int> ordre, occ(N);
    for (int i = 0; i < N; i++)
    {
        if (occ[i])
            continue;
        dfs(i, AR, ordre, occ);
    }
    occ.assign(N, 0);
    vector<int> comp(N), color(N);
    vector<vector<int>> comps;
    for (int i = N - 1; i >= 0; i--)
    {
        if (occ[i])
            continue;
        comps.push_back({});
        dfs2(i, AR2, occ, comp, color, comps, 1);
    }
    vector<int> dep(comps.size());
    vector<vector<int>> AR3(comps.size());
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < AR[i].size(); j++)
        {
            if (comp[i] != comp[AR[i][j]])
                AR3[comp[AR[i][j]]].push_back(comp[i]);
            else
                left[i]++;
        }
    }
    queue<int> Q;
    for (int i = 0; i < comps.size(); i++)
    {
        sort(AR3[i].begin(), AR3[i].end());
        vector<int> temp;
        for (int j = 0; j < AR3[i].size(); j++)
            if (j == 0 || AR3[i][j] != AR3[i][j - 1])
            {
                temp.push_back(AR3[i][j]);
                dep[AR3[i][j]]++;
            }
        swap(temp, AR3[i]);
        if (dep[i] == 0)
            Q.push(i);
    }
    vector<int> ans(N);
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        queue<pair<int, int>> Q2;
        for (int i = 0; i < comps[x].size(); i++)
        {
            int y = comps[x][i];
            for (int j = 0; j < AR[y].size(); j++)
            {
                if (ans[AR[y][j]] == 1)
                    Q2.push({y, 0});
            }
        }
        while (!Q2.empty())
        {
            int y = Q2.front().first, t = Q2.front().second;
            Q2.pop();
            if (t)
            {
                ans[y] = 1;
                for (int i = 0; i < AR2[y].size(); i++)
                {
                    if (comp[AR2[y][i]] != x)
                        continue;
                    if (left[AR2[y][i]])
                        Q2.push({AR2[y][i], 0});
                    left[AR2[y][i]] = 0;
                }
            }
            else
            {
                ans[y] = -1;
                for (int i = 0; i < AR2[y].size(); i++)
                {
                    if (comp[AR2[y][i]] != x)
                        continue;
                    left[AR2[y][i]]--;
                    if (left[AR2[y][i]] == 0)
                        Q2.push({AR2[y][i], 1});
                }
            }
        }
        for (int i = 0; i < comps[x].size(); i++)
        {
            if (ans[comps[x][i]] == 0)
                ans[comps[x][i]] = color[comps[x][i]];
        }
        for (int i = 0; i < AR3[x].size(); i++)
        {
            dep[AR3[x][i]]--;
            if (dep[AR3[x][i]] == 0)
                Q.push(AR3[x][i]);
        }
    }
    int tot = 0;
    for (int i = 0; i < N; i++)
        if (ans[i] == 1)
            tot++;
    cout << tot << '\n';
    for (int i = 0; i < N; i++)
        if (ans[i] == 1)
            cout << i + 1 << ' ';
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33