Submission #293696

#	Time	Username	Problem	Language	Result	Execution time	Memory
293696		Kastanda	Simurgh (IOI17_simurgh)	C++11	100 / 100	277 ms	7544 KiB

simurgh

// M
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 505, MXM = N * N / 2;
int n, m, A[MXM], B[MXM], Stat[MXM];
int P[N], PE[N], H[N], F[N], M[N], Back[MXM];
vector < pair < int , int > > Adj[N];
void DFS(int v, int p, int pe)
{
        M[v] = 1;
        P[v] = p;
        PE[v] = pe;
        for (auto e : Adj[v])
        {
                int u = e.first;
                int id = e.second;
                if (id == pe)
                        continue;
                if (!M[u])
                {
                        H[u] = H[v] + 1;
                        DFS(u, v, id);
                }
                else if (M[u] == 1)
                {
                        int nw = v;
                        while (nw != u)
                        {
                                if (Back[PE[nw]] == -1)
                                        Back[PE[nw]] = id;
                                nw = P[nw];
                        }
                }
        }
        M[v] = 2;
}
int Find(int v)
{
        return (F[v] < 0 ? v : (F[v] = Find(F[v])));
}
inline int Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return 0;
        F[v] = u;
        return 1;
}

vector < int > find_roads(int _n, vector < int > _u, vector < int > _v)
{
        n = _n;
        m = (int)_u.size();
        for (int i = 0; i < m; i ++)
                A[i] = _u[i], B[i] = _v[i];

        for (int i = 0; i < m; i ++)
        {
                Adj[A[i]].push_back({B[i], i});
                Adj[B[i]].push_back({A[i], i});
        }

        memset(Stat, -1, sizeof(Stat));
        memset(Back, -1, sizeof(Back));
        DFS(0, -1, -1);

        for (int i = 1; i < n; i ++)
                if (Stat[PE[i]] == -1)
                {
                        int e = Back[PE[i]];
                        if (e == -1)
                        {
                                Stat[PE[i]] = 1;
                                continue;
                        }
                        int v = A[e], u = B[e];
                        if (H[v] < H[u])
                                swap(v, u);
                        int nw = v;
                        vector < int > V, R;
                        memset(M, 0, sizeof(M));
                        while (nw != u)
                        {
                                if (Stat[PE[nw]] == -1)
                                        V.push_back(PE[nw]);
                                else
                                        R.push_back(PE[nw]);
                                M[nw] = 1;
                                nw = P[nw];
                        }
                        assert((int)V.size());
                        V.push_back(e);
                        vector < int > T;
                        for (int j = 1; j < n; j ++)
                                if (!M[j])
                                        T.push_back(PE[j]);
                        if (!R.size())
                        {
                                int mn = n, mx = -1;
                                vector < int > Val(n, 0);
                                for (int j = 0; j < (int)V.size(); j ++)
                                {
                                        vector < int > TMp = T;
                                        for (int h = 0; h < (int)V.size(); h ++)
                                                if (j != h)
                                                        TMp.push_back(V[h]);
                                        assert((int)TMp.size() == n - 1);
                                        Val[j] = count_common_roads(TMp);
                                        mn = min(mn, Val[j]);
                                        mx = max(mx, Val[j]);
                                }
                                if (mn == mx)
                                        for (int j : V)
                                                Stat[j] = 0;
                                else
                                {
                                        for (int j = 0; j < (int)V.size(); j ++)
                                                if (Val[j] == mn)
                                                        Stat[V[j]] = 1;
                                                else
                                                        Stat[V[j]] = 0;
                                }
                        }
                        else
                        {
                                vector < int > TMp = T;
                                for (int j : R)
                                        if (j != R[0])
                                                TMp.push_back(j);
                                for (int j : V)
                                        TMp.push_back(j);
                                assert(TMp.size() == n - 1);
                                int val = count_common_roads(TMp);

                                for (int j = 0; j < (int)V.size(); j ++)
                                {
                                        TMp = T;
                                        for (int h = 0; h < (int)V.size(); h ++)
                                                if (j != h)
                                                        TMp.push_back(V[h]);
                                        for (int h : R)
                                                TMp.push_back(h);
                                        assert((int)TMp.size() == n - 1);
                                        int cnt = count_common_roads(TMp);
                                        if (cnt < val)
                                                Stat[V[j]] = 1;
                                        else if (cnt > val)
                                                Stat[V[j]] = 0;
                                        else
                                                Stat[V[j]] = Stat[R[0]];
                                }
                        }
                }

        for (int i = 1; i < n; i ++)
                assert(Stat[PE[i]] != -1);

        for (int i = 1; i <= n; i ++)
        {
                vector < int > vec;
                for (auto u : Adj[i])
                        if (Stat[u.second] == -1)
                                vec.push_back(u.second);

                auto Ask = [&](int l, int r){
                        vector < int > TMp;
                        memset(F, -1, sizeof(F));
                        for (int j = l; j < r; j ++)
                        {
                                TMp.push_back(vec[j]);
                                Merge(A[vec[j]], B[vec[j]]);
                        }
                        int c = 0;
                        for (int i = 1; i < n; i ++)
                                if (Merge(i, P[i]))
                                        TMp.push_back(PE[i]), c -= Stat[PE[i]];
                        c += count_common_roads(TMp);
                        return c;
                };

                int d = Ask(0, (int)vec.size());

                int le = -1, ri = (int)vec.size(), md;
                for (int __ = 0; __ < d; __ ++)
                {
                        le ++;
                        ri = (int)vec.size();
                        while (ri - le > 1)
                        {
                                md = (le + ri) >> 1;
                                if (Ask(le, md))
                                        ri = md;
                                else
                                        le = md;
                        }
                        assert(Ask(le, le + 1));
                        Stat[vec[le]] = 1;
                }
                for (int id : vec)
                        if (Stat[id] == -1)
                                Stat[id] = 0;
        }

        vector < int > Rs;
        for (int i = 0; i < m; i ++)
                if (Stat[i])
                        Rs.push_back(i);
        return Rs;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:134:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |                                 assert(TMp.size() == n - 1);
      |                                        ~~~~~~~~~~~^~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30