oj.uz

답안 #1009365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009365 2024-06-27T12:08:14 Z boris_mihov Simurgh (IOI17_simurgh) C++17
30 / 100
 229 ms 159232 KB 
#include "simurgh.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>

typedef long long llong;
const int MAXN = 1000 + 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);
    // 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;
        }

        // std::cout << "apply cover"
        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.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;
        }

        // 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;
            }
        }
    }
    // std::cout << "done with for\n" << std::flush;
    for (int u = 0 ; u < n ; ++u)
    {
        std::vector <std::pair <int,int>> allEdges;
        for (const int &v : g[u])
        {
            // std::cout << "foooor: " << u << ' ' << v << '\n' << std::flush;
            if (isInTree[u][v] || v < u)
            {
                continue;
            }

            // std::cout << "push baaaack: " << u << ' ' << v << '\n' << std::flush;
            allEdges.push_back({u, v});
        }

        // std::cout << "done for: " << std::flush;
        // std::cout << "done for: " << u << " = " << -1 << '\n' << std::flush;
        int lastPos = -1;
        // std::cout << "cnt for: " << u << " = " << -1 << '\n' << std::flush;
        int countFound = 0;
        // std::cout << "cnt for: " << u << " = " << -1 << '\n' << std::flush;
            // std::cout << "here\n"; exit(0);
        if (allEdges.empty()) continue;
        int cnt = treeIncluding(allEdges);
        // std::cout << "cnt for: " << u << " = " << cnt << '\n' << std::flush;
        while (cnt--)
        {
            int l = lastPos, r = allEdges.size(), mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                assert(0 <= mid && mid < r);
                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;
}

Compilation message

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

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33372 KB correct
2 Correct 5 ms 33372 KB correct
3 Correct 6 ms 33368 KB correct
4 Correct 7 ms 33388 KB correct
5 Correct 6 ms 33412 KB correct
6 Correct 5 ms 33372 KB correct
7 Correct 6 ms 33372 KB correct
8 Correct 6 ms 33372 KB correct
9 Correct 5 ms 33368 KB correct
10 Correct 5 ms 33372 KB correct
11 Correct 6 ms 33372 KB correct
12 Correct 6 ms 33372 KB correct
13 Correct 5 ms 33372 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33372 KB correct
2 Correct 5 ms 33372 KB correct
3 Correct 6 ms 33368 KB correct
4 Correct 7 ms 33388 KB correct
5 Correct 6 ms 33412 KB correct
6 Correct 5 ms 33372 KB correct
7 Correct 6 ms 33372 KB correct
8 Correct 6 ms 33372 KB correct
9 Correct 5 ms 33368 KB correct
10 Correct 5 ms 33372 KB correct
11 Correct 6 ms 33372 KB correct
12 Correct 6 ms 33372 KB correct
13 Correct 5 ms 33372 KB correct
14 Correct 8 ms 33884 KB correct
15 Correct 10 ms 33884 KB correct
16 Correct 8 ms 33896 KB correct
17 Correct 8 ms 33628 KB correct
18 Correct 6 ms 33628 KB correct
19 Correct 7 ms 33628 KB correct
20 Correct 7 ms 33672 KB correct
21 Correct 7 ms 33628 KB correct
22 Correct 7 ms 33628 KB correct
23 Correct 6 ms 33552 KB correct
24 Correct 7 ms 33624 KB correct
25 Correct 6 ms 33628 KB correct
26 Correct 6 ms 33628 KB correct
27 Correct 7 ms 33628 KB correct
28 Correct 6 ms 33628 KB correct
29 Correct 7 ms 33628 KB correct
30 Correct 7 ms 33628 KB correct
31 Correct 7 ms 33624 KB correct
32 Correct 7 ms 33628 KB correct
33 Correct 7 ms 33644 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33372 KB correct
2 Correct 5 ms 33372 KB correct
3 Correct 6 ms 33368 KB correct
4 Correct 7 ms 33388 KB correct
5 Correct 6 ms 33412 KB correct
6 Correct 5 ms 33372 KB correct
7 Correct 6 ms 33372 KB correct
8 Correct 6 ms 33372 KB correct
9 Correct 5 ms 33368 KB correct
10 Correct 5 ms 33372 KB correct
11 Correct 6 ms 33372 KB correct
12 Correct 6 ms 33372 KB correct
13 Correct 5 ms 33372 KB correct
14 Correct 8 ms 33884 KB correct
15 Correct 10 ms 33884 KB correct
16 Correct 8 ms 33896 KB correct
17 Correct 8 ms 33628 KB correct
18 Correct 6 ms 33628 KB correct
19 Correct 7 ms 33628 KB correct
20 Correct 7 ms 33672 KB correct
21 Correct 7 ms 33628 KB correct
22 Correct 7 ms 33628 KB correct
23 Correct 6 ms 33552 KB correct
24 Correct 7 ms 33624 KB correct
25 Correct 6 ms 33628 KB correct
26 Correct 6 ms 33628 KB correct
27 Correct 7 ms 33628 KB correct
28 Correct 6 ms 33628 KB correct
29 Correct 7 ms 33628 KB correct
30 Correct 7 ms 33628 KB correct
31 Correct 7 ms 33624 KB correct
32 Correct 7 ms 33628 KB correct
33 Correct 7 ms 33644 KB correct
34 Incorrect 167 ms 61012 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33368 KB correct
2 Correct 6 ms 33368 KB correct
3 Incorrect 229 ms 159232 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 33372 KB correct
2 Correct 5 ms 33372 KB correct
3 Correct 6 ms 33368 KB correct
4 Correct 7 ms 33388 KB correct
5 Correct 6 ms 33412 KB correct
6 Correct 5 ms 33372 KB correct
7 Correct 6 ms 33372 KB correct
8 Correct 6 ms 33372 KB correct
9 Correct 5 ms 33368 KB correct
10 Correct 5 ms 33372 KB correct
11 Correct 6 ms 33372 KB correct
12 Correct 6 ms 33372 KB correct
13 Correct 5 ms 33372 KB correct
14 Correct 8 ms 33884 KB correct
15 Correct 10 ms 33884 KB correct
16 Correct 8 ms 33896 KB correct
17 Correct 8 ms 33628 KB correct
18 Correct 6 ms 33628 KB correct
19 Correct 7 ms 33628 KB correct
20 Correct 7 ms 33672 KB correct
21 Correct 7 ms 33628 KB correct
22 Correct 7 ms 33628 KB correct
23 Correct 6 ms 33552 KB correct
24 Correct 7 ms 33624 KB correct
25 Correct 6 ms 33628 KB correct
26 Correct 6 ms 33628 KB correct
27 Correct 7 ms 33628 KB correct
28 Correct 6 ms 33628 KB correct
29 Correct 7 ms 33628 KB correct
30 Correct 7 ms 33628 KB correct
31 Correct 7 ms 33624 KB correct
32 Correct 7 ms 33628 KB correct
33 Correct 7 ms 33644 KB correct
34 Incorrect 167 ms 61012 KB WA in grader: NO
35 Halted 0 ms 0 KB -