Submission #802984

#	Time	Username	Problem	Language	Result	Execution time	Memory
802984		SamAnd	Keys (IOI21_keys)	C++17	100 / 100	2021 ms	395340 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 300005;

int n;
vector<pair<int, int> > g[N];

int c[N];
bool cc[N];
vector<int> v[N];
vector<vector<int> > vvv;
int stup(int x, const vector<int>& r)
{
    int ans = 0;
    queue<int> q;
    q.push(x);
    queue<int> qq;
    vector<int> vv;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (c[x])
            continue;
        ++ans;
        vv.push_back(x);
        qq.push(x);
        qq.push(r[x]);
        c[x] = true;
        cc[r[x]] = true;
        while (!v[r[x]].empty())
        {
            q.push(v[r[x]].back());
            v[r[x]].pop_back();
        }
        for (int i = 0; i < sz(g[x]); ++i)
        {
            int h = g[x][i].fi;
            if (cc[g[x][i].se])
                q.push(h);
            else
            {
                qq.push(g[x][i].se);
                v[g[x][i].se].push_back(h);
            }
        }
    }
    while (!qq.empty())
    {
        int x = qq.front();
        qq.pop();
        c[x] = false;
        cc[x] = false;
        v[x].clear();
    }
    vvv.push_back(vv);
    return ans;
}

int u[N];
vector<vector<int> > vv;
bool dfs(int x)
{
    c[x] = 1;
    if (!c[u[x]])
    {
        if (dfs(u[x]))
        {
            c[x] = 2;
            return true;
        }
    }
    if (c[u[x]] == 1)
    {
        vector<int> v;
        int y = u[x];
        while (y != x)
        {
            v.push_back(y);
            y = u[y];
        }
        v.push_back(x);
        vv.push_back(v);
        c[x] = 2;
        return true;
    }
    c[x] = 2;
    return false;
}

std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
    n = sz(R);
    int m = sz(U);

	std::vector<int> ans(n, 0);
    for (int i = 0; i < m; ++i)
    {
        int x = U[i];
        int y = V[i];
        if (x == y)
            continue;
        g[x].push_back(m_p(y, C[i]));
        g[y].push_back(m_p(x, C[i]));
    }

    bool ff = false;
    for (int x = 0; x < n; ++x)
    {
        bool f = false;
        for (int i = 0; i < g[x].size(); ++i)
        {
            if (g[x][i].se == R[x])
            {
                u[x] = g[x][i].fi;
                f = true;
                break;
            }
        }
        if (!f)
        {
            ff = true;
            break;
        }
    }

    if (ff)
    {
        for (int x = 0; x < n; ++x)
        {
            bool f = false;
            for (int i = 0; i < g[x].size(); ++i)
            {
                if (g[x][i].se == R[x])
                {
                    f = true;
                    break;
                }
            }
            if (!f)
                ans[x] = 1;
        }
        return ans;
    }

    for (int x = 0; x < n; ++x)
    {
        if (!c[x])
        {
            dfs(x);
        }
    }

    for (int x = 0; x < n; ++x)
        c[x] = false;

    vector<int> s;
    for (int i = 0; i < sz(vv); ++i)
    {
        s.push_back(stup(vv[i][0], R));
    }

    int minu = s[0];
    for (int i = 0; i < sz(vv); ++i)
        minu = min(minu, s[i]);

    for (int i = 0; i < sz(vv); ++i)
    {
        if (s[i] == minu)
        {
            for (int j = 0; j < sz(vvv[i]); ++j)
                ans[vvv[i][j]] = 1;
        }
    }

    return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int i = 0; i < g[x].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
keys.cpp:136:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for (int i = 0; i < g[x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33