Submission #53713

#	Time	Username	Problem	Language	Result	Execution time	Memory
53713		fallingstar	Simurgh (IOI17_simurgh)	C++14	0 / 100	3 ms	472 KiB

simurgh

#include "simurgh.h"

#include <cassert>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int N = 240 + 2;

int n;
int eid[N][N];
bool royal[N][N];

struct TEdge { int u, v, id; };
vector<TEdge> el;

vector<TEdge*> SpanningTree(const vector<TEdge*> &elist)
{
    vector<int> cpn(n);
    for (int i = 0; i < n; ++i) cpn[i] = i;
    vector<TEdge*> ret;
    for (auto e: elist)
        if (cpn[e->u] != cpn[e->v])
        {
            int old_cpn = cpn[e->v];
            for (int i = 0; i < n; ++i)
                if (cpn[i] == old_cpn) cpn[i] = cpn[e->u];
            ret.push_back(e);
        }
    return ret;
}

int col[N];
vector<int> g[N];

void Dfs(int u)
{
    for (int v: g[u])
        if (col[v] == -1) 
        {
            col[v] = col[u];
            Dfs(v);
        }
}

vector<int> find_roads(int n_, vector<int> roadsU, vector<int> roadsV)
{
    n = n_;
    int m = roadsU.size();
    for (int i = 0; i < n; ++i)
        fill(eid[i], eid[i] + n, -1);
    for (int i = 0; i < m; ++i)
    {
        int u = roadsU[i], v = roadsV[i];
        el.push_back({u, v, i});
        eid[u][v] = eid[v][u] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        vector<TEdge*> span;
        for (auto &e: el)
            if (e.u != i && e.v != i) span.push_back(&e);
        for (auto &e: el)
            if (e.u == i || e.v == i) span.push_back(&e);
        vector<TEdge*> base = SpanningTree(span);
        assert(base.size() == n - 1);
   /*      if (i == -1) cout << base[0]; */
        for (int j = 0; j < n; ++j) g[j].clear(), col[j] = -1;
        set<int> ids;
        for (auto e: base)
        {
            g[e->u].push_back(e->v);
            g[e->v].push_back(e->u);
            ids.insert(e->id);
        }
        col[i] = i;
        for (int v: g[i]) if (col[v] == -1) col[v] = v, Dfs(v);
        int baseCnt = count_common_roads(vector<int>(ids.begin(), ids.end()));
        for (int u: g[i])
        {
            int posiCnt = -1;
            if (u < i) posiCnt = baseCnt + !royal[i][u];
            for (int v = 0; posiCnt == -1 && v < i; ++v)
                if (col[v] == u && eid[i][v] != -1)
                {
                    ids.erase(eid[i][u]);
                    ids.insert(eid[i][v]);
                    posiCnt = count_common_roads(vector<int>(ids.begin(), ids.end()));
                    ids.erase(eid[i][v]);
                    ids.insert(eid[i][u]);
                }
            
            vector<int> adj;
            if (posiCnt == -1)
            {
                int mx = baseCnt;
                adj.push_back(u);
                for (int v = i + 1; v < n; ++v)
                    if (col[v] == u && eid[i][v] != -1)
                    {
                        ids.erase(eid[i][u]);
                        ids.insert(eid[i][v]);
                        int inq = count_common_roads(vector<int>(ids.begin(), ids.end()));
                        if (inq > mx) adj.clear(), mx = inq;
                        if (inq == mx) adj.push_back(v);
                        ids.erase(eid[i][v]);
                        ids.insert(eid[i][u]);
                    }
            }
            else 
                for (int v = i + 1; v < n; ++v)
                    if (col[v] == u && eid[i][v] != -1)
                    {
                        ids.erase(eid[i][u]);
                        ids.insert(eid[i][v]);
                        if (count_common_roads(vector<int>(ids.begin(), ids.end())) == posiCnt) adj.push_back(v);
                        ids.erase(eid[i][v]);
                        ids.insert(eid[i][u]);
                    }
            for (int v: adj)
                royal[i][v] = royal[v][i] = true;
        }
    }
    vector<int> res;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (royal[i][j]) res.push_back(eid[i][j]);
    return res;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from simurgh.cpp:3:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:68:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(base.size() == n - 1);
                ~~~~~~~~~~~~^~~~~~~~

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