Submission #293089

#	Time	Username	Problem	Language	Result	Execution time	Memory
293089		Kastanda	Simurgh (IOI17_simurgh)	C++11	30 / 100	3076 ms	3448 KiB

simurgh

// M
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 245, MXM = N * N / 2;
int n, m, A[MXM], B[MXM];
bool Del[MXM], Sure[MXM], MR[N];
char M[N];
int P[N], PE[N];
vector < int > Tre, Cyc;
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 || Del[id])
                        continue;
                if (Sure[id] && !M[u])
                        DFS(u, v, id);
        }*/
        for (auto e : Adj[v])
        {
                int u = e.first;
                int id = e.second;
                if (id == pe || Del[id])
                        continue;
                //if (Sure[id])
                        //continue;
                if (!M[u])
                        DFS(u, v, id);
                else if (M[u] == 1 && !Cyc.size())
                {
                        int nw = v;
                        while (nw != u)
                        {
                                if (!Sure[PE[nw]])
                                        Cyc.push_back(PE[nw]);
                                else
                                        Tre.push_back(PE[nw]);
                                MR[nw] = 1;
                                nw = P[nw];
                        }
                        if (!Sure[id])
                                Cyc.push_back(id);
                        else
                                Tre.push_back(id);
                }
        }
        if (pe != -1 && !MR[v])
                Tre.push_back(pe);
        M[v] = 2;
}

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});
        }
        assert(m <= 3e4);

        int sre = 0;
        while (true)
        {
                Tre.clear();
                Cyc.clear();
                memset(M, 0, sizeof(M));
                memset(MR, 0, sizeof(MR));
                DFS(0, -1, -1);
                if (!Cyc.size())
                        break;
                vector < int > Val(n + 1, -1);
                int mx = -1, mn = n;
                for (int i = 0; i < (int)Cyc.size(); i ++)
                {
                        vector < int > tmp = Tre;
                        for (int j = 0; j < (int)Cyc.size(); j ++)
                                if (i != j)
                                        tmp.push_back(Cyc[j]);
                        assert(tmp.size() == n - 1);
                        Val[i] = count_common_roads(tmp);

                        /*printf("Asking :: %d || ", Val[i]);
                        for (int j : tmp)
                                printf("%d ", j);
                        printf("\n");*/

                        mn = min(mn, Val[i]);
                        mx = max(mx, Val[i]);
                }
                for (int i = 0; i < (int)Cyc.size(); i ++)
                        if (Val[i] == mx)
                                Del[Cyc[i]] = 1;
                if (mn < mx)
                {
                        for (int i = 0; i < (int)Cyc.size(); i ++)
                                if (Val[i] == mn && !Sure[Cyc[i]])
                                        Sure[Cyc[i]] = 1, sre ++;
                }
                if (sre == n - 1)
                {
                        vector < int > vec;
                        for (int i = 0; i < m; i ++)
                                if (Sure[i])
                                        vec.push_back(i);
                        return vec;
                }
        }
        vector < int > vec;
        for (int i = 0; i < m; i ++)
                if (Del[i] == 0)
                        vec.push_back(i);
        assert(vec.size() == n - 1);
        return vec;
}

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:91:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |                         assert(tmp.size() == n - 1);
      |                                ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:124:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |         assert(vec.size() == n - 1);
      |                ~~~~~~~~~~~^~~~~~~~

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