Submission #879922

#	Time	Username	Problem	Language	Result	Execution time	Memory
879922		grafff	Keys (IOI21_keys)	C++17	37 / 100	3063 ms	252668 KiB

keys

#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define xc first
#define yc second
#define ll long long
#define LM LLONG_MAX
#define Lm LLONG_MIM
#define IM INT_MAX
#define Im INT_MIM
#define pb(x) push_back(x)
#define mk(x,y) make_pair(x,y)

using namespace std;

int mn, n, m;
vector <int> r, a;
map <ll, vector <ll>> st, fn, gr, tr, nv;
map <ll, vector <bool>> uses;

ll dfs(ll x)
{
    map <ll, bool> fk;
    vector <bool> fv(n);
    ll col = 1;
    vector <ll> o = {x};
    fv[x] = true;
    while(o.size() > 0)
    {
        if(!fk[r[o[0]]])
        {
            fk[r[o[0]]] = true;
            for(int i = 0; i < st[r[o[0]]].size(); i++)
            {
                if(fv[st[r[o[0]]][i]] && !fv[fn[r[o[0]]][i]])
                {
                    if(a[fn[r[o[0]]][i]] > mn)
                    {
                        uses[x] = uses[fn[r[o[0]]][i]];
                        return mn + 1;
                    }
                    if(a[fn[r[o[0]]][i]] == mn)
                    {
                        if(uses[fn[r[o[0]]][i]][x])
                        {
                            uses[x] = uses[fn[r[o[0]]][i]];
                            return mn;
                        }
                        else
                        {
                            uses[x] = fv;
                            return mn + 1;
                        }
                    }
                    o.pb(fn[r[o[0]]][i]);
                    fv[fn[r[o[0]]][i]] = true;
                    col++;
                    if(col > mn)
                    {
                        uses[x] = fv;
                        return col;
                    }
                }
            }
        }
        fk[r[o[0]]] = true;
        for(int i = 0; i < gr[o[0]].size(); i++)
        {
            if(fk[tr[o[0]][i]] && !fv[gr[o[0]][i]])
            {
                if(a[gr[o[0]][i]] > mn)
                {
                    uses[x] = uses[gr[o[0]][i]];
                    return mn + 1;
                }
                if(a[gr[o[0]][i]] == mn)
                {
                    if(uses[gr[o[0]][i]][x])
                    {
                        uses[x] = uses[gr[o[0]][i]];
                        return mn;
                    }
                    else
                    {
                        uses[x] = fv;
                        return mn + 1;
                    }
                }
                o.pb(gr[o[0]][i]);
                fv[gr[o[0]][i]] = true;
                col++;
                if(col > mn)
                {
                    uses[x] = fv;
                    return col;
                }
            }
        }
        o.erase(o.begin());
    }
    uses[x] = fv;
    return col;
};

vector <int> find_reachable(vector <int> r1, vector <int> u, vector <int> v, vector <int> c)
{
    mn = IM;
    int mx = 0;
    r = r1;
    n = r.size();
    m = v.size();
    for(int i = 0; i < m; i++)
    {
        mx = max(mx, c[i]);
        st[c[i]].pb(v[i]);
        fn[c[i]].pb(u[i]);
        st[c[i]].pb(u[i]);
        fn[c[i]].pb(v[i]);
        gr[u[i]].pb(v[i]);
        tr[u[i]].pb(c[i]);
        gr[v[i]].pb(u[i]);
        tr[v[i]].pb(c[i]);
    }
    a.resize(n);
    for(int i = 0; i < n; i++)
    {
        a[i] = dfs(i);
        mn = min(a[i], mn);
    }
    for(int i = 0; i < n; i++)
    {
        a[i] = (a[i] == mn);
    }
    return a;
};

/**
int main ()
{
    //vector <int> vec_prov1 = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
    //vector <int> vec_prov2 = find_reachable({0, 0, 0}, {0}, {1}, {0});
    vector <int> vec_prov3 = find_reachable({0, 1, 1, 2, 2, 1, 2}, {0, 0, 1, 1, 2, 3, 3, 4, 4, 5}, {1, 2, 2, 3, 3, 4, 5, 5, 6, 6}, {0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
    for(int i : vec_prov3)
    {
        cout << i << " ";
    }
    cout << endl;
}/**/

Compilation message (stderr)

keys.cpp:148:2: warning: "/*" within comment [-Wcomment]
  148 | }/**/
      |   
keys.cpp: In function 'long long int dfs(long long int)':
keys.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int i = 0; i < st[r[o[0]]].size(); i++)
      |                            ~~^~~~~~~~~~~~~~~~~~~~
keys.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i = 0; i < gr[o[0]].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~

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