제출 #1009367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009367		boris_mihov	Simurgh (IOI17_simurgh)	C++17	100 / 100	394 ms	250376 KiB

simurgh

#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>

typedef long long llong;
const int MAXN = 500 + 12;

namespace
{
    int n;
    int dep[MAXN];
    int par[MAXN];
    bool vis[MAXN];
    int idx[MAXN][MAXN];
    int covering[MAXN][MAXN];
    bool queried[MAXN][MAXN];
    bool isIn[MAXN][MAXN];
    bool isInTree[MAXN][MAXN];
    std::vector <int> g[MAXN];
    std::vector <int> t[MAXN];
    std::vector <std::pair <int,int>> byCovering[MAXN * MAXN];
    std::vector <std::pair <int,int>> inTreeEdges;
    std::vector <int> inTree;
}

struct DSU
{
    int p[MAXN];
    int dep[MAXN];

    void reset()
    {
        std::iota(p, p + n, 0);
        std::fill(dep, dep + n, 1);
    }

    int find(int node)
    {
        assert(node != -1);
        if (p[node] == node) return node;
        return p[node] = find(p[node]);
    }

    void connect(int u, int v)
    {
        u = find(u);
        v = find(v);
        assert(u != v);
        assert(u >= 0 && v >= 0);

        if (u == v)
        {
            return;
        }

        if (dep[u] > dep[v])
        {
            std::swap(u, v);
        }

        if (dep[u] == dep[v])
        {
            dep[v]++;
        }

        p[u] = v;
    }

    bool areConnected(int u, int v)
    {
        assert(u >= 0 && v >= 0);
        return find(u) == find(v);
    }
};

DSU dsu;
void depthDFS(int node, int p)
{
    par[node] = p;
    vis[node] = true;
    for (const int &u : g[node])
    {
        if (u == p || vis[u])
        {
            continue;
        }

        dep[u] = dep[node] + 1;
        t[node].push_back(u);
        isInTree[node][u] = true;
        isInTree[u][node] = true;
        inTree.push_back(idx[u][node]);
        inTreeEdges.push_back({u, node});
        depthDFS(u, node);
    }
}

void apply(int u, int v, int idx)
{
    if (u == v)
    {
        return;
    }

    byCovering[idx].push_back({u, par[u]});
    covering[u][par[u]] = idx;
    apply(par[u], v, idx);
}

void dfsCovering(int node)
{
    if (node != 0)
    {
        if (covering[node][par[node]] == -1) 
        {
            isIn[node][par[node]] = true;
            isIn[par[node]][node] = true;
        }
    }

    for (const int &u : t[node])
    {
        dfsCovering(u);
    }
}

int treeIncluding(std::vector <std::pair <int,int>> &edges)
{
    
    dsu.reset();
    std::vector <int> indices;
    // std::cout << "tree including:\n";
    // for (const auto &[u, v] : edges)
    // {
    //     std::cout << u << ' ' << v << '\n';
    // }

    // std::cout << std::flush;
    // exit(0);
    for (const auto &[u, v] : edges)
    {
        assert(!dsu.areConnected(u, v));
        dsu.connect(u, v);
        indices.push_back(idx[u][v]);
    }

    int sub = 0;
    for (const auto &[u, v] : inTreeEdges)
    {
        if (dsu.areConnected(u, v))
        {
            continue;
        }

        sub += isIn[u][v];
        indices.push_back(idx[u][v]);
        dsu.connect(u, v);
    }  

    return count_common_roads(indices) - sub;
}

std::vector <int> find_roads(int n, std::vector <int> u, std::vector <int> v) 
{ 
    ::n = n;
    memset(idx, -1, sizeof(idx));
    memset(covering, -1, sizeof(covering));
    for (int i = 0 ; i < u.size() ; ++i)
    {
        idx[u[i]][v[i]] = i;
        idx[v[i]][u[i]] = i;
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }

    depthDFS(0, -1);
    for (int i = 0 ; i < u.size() ; ++i)
    {
        if (isInTree[u[i]][v[i]])
        {
            continue;
        }

        if (dep[u[i]] > dep[v[i]]) apply(u[i], v[i], i);
        else apply(v[i], u[i], i);
    }

    dfsCovering(0);
    int globalTreeCount = count_common_roads(inTree);
    if (globalTreeCount == n - 1)
    {
        return inTree;
    }

    for (int coverIdx = 0 ; coverIdx < u.size() ; ++coverIdx)
    {
        int countUnanswered = 0;
        for (const auto &[u, v] : byCovering[coverIdx])
        {
            countUnanswered += !queried[u][v];
        }

        if (countUnanswered == 0)
        {
            continue;
        }

        int res = globalTreeCount;
        std::vector <int> sols;
        bool foundMAX = false;
        for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
        {
            if (queried[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second] && (foundMAX || isIn[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second]))
            {
                sols.push_back(MAXN);
                continue;
            }

            std::vector <int> curr = inTree;
            for (int &j : curr)
            {
                if (j == idx[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second])
                {
                    std::swap(j, curr.back());
                    curr.pop_back();
                    break;
                }
            }

            curr.push_back(coverIdx);
            sols.push_back(count_common_roads(curr));
            res = std::max(res, sols.back());

            if (queried[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second])
            {
                foundMAX = true;
            }

            queried[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second] = true;
            queried[byCovering[coverIdx][i].second][byCovering[coverIdx][i].first] = true;
        }

        for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
        {
            if (sols[i] < res)
            {
                isIn[byCovering[coverIdx][i].first][byCovering[coverIdx][i].second] = true;
                isIn[byCovering[coverIdx][i].second][byCovering[coverIdx][i].first] = true;
            }
        }
    }
    for (int u = 0 ; u < n ; ++u)
    {
        std::vector <std::pair <int,int>> allEdges;
        for (const int &v : g[u])
        {
            if (isInTree[u][v] || v < u)
            {
                continue;
            }

            allEdges.push_back({u, v});
        }

        if (allEdges.empty()) continue;
        
        int lastPos = -1;
        int countFound = 0;
        int cnt = treeIncluding(allEdges);

        while (cnt--)
        {
            int l = lastPos, r = allEdges.size(), mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                std::vector <std::pair <int,int>> curr;
                for (int i = 0 ; i <= mid ; ++i)
                {
                    curr.push_back(allEdges[i]);
                }

                if (treeIncluding(curr) <= countFound) l = mid;
                else r = mid;
            }

            assert(0 <= r && r < allEdges.size());
            isIn[u][allEdges[r].second] = true;
            isIn[allEdges[r].second][u] = true;
            countFound++;
            lastPos = r;
        }
    }

    std::vector <int> sol;
    for (int i = 0 ; i < n ; ++i)
    {
        for (int j = i + 1 ; j < n ; ++j)
        {
            if (isIn[i][j])
            {
                sol.push_back(idx[i][j]);
            }
        }
    }

    // std::cout << "return\n";
    return sol;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:172:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for (int i = 0 ; i < u.size() ; ++i)
      |                      ~~^~~~~~~~~~
simurgh.cpp:181:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for (int i = 0 ; i < u.size() ; ++i)
      |                      ~~^~~~~~~~~~
simurgh.cpp:199:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for (int coverIdx = 0 ; coverIdx < u.size() ; ++coverIdx)
      |                             ~~~~~~~~~^~~~~~~~~~
simurgh.cpp:215:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |         for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:247:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:280:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  280 |                 mid = l + r >> 1;
      |                       ~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from simurgh.cpp:5:
simurgh.cpp:291:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  291 |             assert(0 <= r && r < allEdges.size());
      |                              ~~^~~~~~~~~~~~~~~~~

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