oj.uz

답안 #1009341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009341 2024-06-27T11:44:53 Z boris_mihov Simurgh (IOI17_simurgh) C++17
0 / 100
 11 ms 18776 KB 
#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 par[MAXN];
    int dep[MAXN];

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

    int find(int node)
    {
        if (par[node] == node) return node;
        return par[node] = find(par[node]);
    }

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

        if (u == v)
        {
            return;
        }

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

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

        par[u] = v;
    }

    bool areConnected(int u, int v)
    {
        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;
    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(idx));
    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);
    // std::cout << "in tree\n";
    // for (const auto &[u, v] : inTreeEdges)
    // {
    //     std::cout << u << ' ' << v << '\n';
    // }

    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)
    {
        if (byCovering[coverIdx].empty())
        {
            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[i] = 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;
        }

        // std::cout << "here: " << coverIdx << ' ' << byCovering[coverIdx].size() << '\n';
        for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
        {
            // std::cout <<
            if (sols[i] < res)
            {
                // std::cout << "in golden set: " << byCovering[coverIdx][i].first << ' ' << byCovering[coverIdx][i].second << '\n';
                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});
        }

        int lastPos = -1;
        int countFound = 0;
        int cnt = treeIncluding(allEdges);
        // std::cout << "cnt for: " << u << " = " << cnt << '\n';
        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(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]);
            }
        }
    }

    return sol;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:167:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int i = 0 ; i < u.size() ; ++i)
      |                      ~~^~~~~~~~~~
simurgh.cpp:182:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |     for (int i = 0 ; i < u.size() ; ++i)
      |                      ~~^~~~~~~~~~
simurgh.cpp:200:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for (int coverIdx = 0 ; coverIdx < u.size() ; ++coverIdx)
      |                             ~~~~~~~~~^~~~~~~~~~
simurgh.cpp:210: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]
  210 |         for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:242: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]
  242 |         for (int i = 0 ; i < byCovering[coverIdx].size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:276:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  276 |                 mid = l + r >> 1;
      |                       ~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from simurgh.cpp:5:
simurgh.cpp:287:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  287 |             assert(r < allEdges.size());
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 18776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 18776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 18776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9308 KB correct
2 Runtime error 11 ms 18588 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 18776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -