oj.uz

Submission #1009367

# Submission time Handle Problem Language Result Execution time Memory
1009367 2024-06-27T12:10:20 Z boris_mihov Simurgh (IOI17_simurgh) C++17
100 / 100
 394 ms 250376 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 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;
}

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: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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB correct
2 Correct 2 ms 9308 KB correct
3 Correct 2 ms 9308 KB correct
4 Correct 2 ms 9308 KB correct
5 Correct 2 ms 9308 KB correct
6 Correct 2 ms 9308 KB correct
7 Correct 2 ms 9304 KB correct
8 Correct 1 ms 9308 KB correct
9 Correct 1 ms 9308 KB correct
10 Correct 2 ms 9308 KB correct
11 Correct 2 ms 9308 KB correct
12 Correct 2 ms 9308 KB correct
13 Correct 2 ms 9304 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB correct
2 Correct 2 ms 9308 KB correct
3 Correct 2 ms 9308 KB correct
4 Correct 2 ms 9308 KB correct
5 Correct 2 ms 9308 KB correct
6 Correct 2 ms 9308 KB correct
7 Correct 2 ms 9304 KB correct
8 Correct 1 ms 9308 KB correct
9 Correct 1 ms 9308 KB correct
10 Correct 2 ms 9308 KB correct
11 Correct 2 ms 9308 KB correct
12 Correct 2 ms 9308 KB correct
13 Correct 2 ms 9304 KB correct
14 Correct 3 ms 9564 KB correct
15 Correct 4 ms 9564 KB correct
16 Correct 3 ms 9564 KB correct
17 Correct 2 ms 9564 KB correct
18 Correct 2 ms 9308 KB correct
19 Correct 3 ms 9564 KB correct
20 Correct 3 ms 9564 KB correct
21 Correct 3 ms 9564 KB correct
22 Correct 2 ms 9304 KB correct
23 Correct 2 ms 9308 KB correct
24 Correct 2 ms 9308 KB correct
25 Correct 2 ms 9308 KB correct
26 Correct 2 ms 9300 KB correct
27 Correct 2 ms 9308 KB correct
28 Correct 2 ms 9328 KB correct
29 Correct 2 ms 9308 KB correct
30 Correct 2 ms 9564 KB correct
31 Correct 2 ms 9568 KB correct
32 Correct 3 ms 9564 KB correct
33 Correct 2 ms 9564 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB correct
2 Correct 2 ms 9308 KB correct
3 Correct 2 ms 9308 KB correct
4 Correct 2 ms 9308 KB correct
5 Correct 2 ms 9308 KB correct
6 Correct 2 ms 9308 KB correct
7 Correct 2 ms 9304 KB correct
8 Correct 1 ms 9308 KB correct
9 Correct 1 ms 9308 KB correct
10 Correct 2 ms 9308 KB correct
11 Correct 2 ms 9308 KB correct
12 Correct 2 ms 9308 KB correct
13 Correct 2 ms 9304 KB correct
14 Correct 3 ms 9564 KB correct
15 Correct 4 ms 9564 KB correct
16 Correct 3 ms 9564 KB correct
17 Correct 2 ms 9564 KB correct
18 Correct 2 ms 9308 KB correct
19 Correct 3 ms 9564 KB correct
20 Correct 3 ms 9564 KB correct
21 Correct 3 ms 9564 KB correct
22 Correct 2 ms 9304 KB correct
23 Correct 2 ms 9308 KB correct
24 Correct 2 ms 9308 KB correct
25 Correct 2 ms 9308 KB correct
26 Correct 2 ms 9300 KB correct
27 Correct 2 ms 9308 KB correct
28 Correct 2 ms 9328 KB correct
29 Correct 2 ms 9308 KB correct
30 Correct 2 ms 9564 KB correct
31 Correct 2 ms 9568 KB correct
32 Correct 3 ms 9564 KB correct
33 Correct 2 ms 9564 KB correct
34 Correct 54 ms 36512 KB correct
35 Correct 53 ms 35724 KB correct
36 Correct 40 ms 27480 KB correct
37 Correct 8 ms 10332 KB correct
38 Correct 55 ms 36312 KB correct
39 Correct 48 ms 32320 KB correct
40 Correct 39 ms 27472 KB correct
41 Correct 54 ms 36640 KB correct
42 Correct 52 ms 36464 KB correct
43 Correct 21 ms 18012 KB correct
44 Correct 16 ms 14936 KB correct
45 Correct 17 ms 16476 KB correct
46 Correct 14 ms 13828 KB correct
47 Correct 8 ms 10332 KB correct
48 Correct 3 ms 9308 KB correct
49 Correct 4 ms 9592 KB correct
50 Correct 8 ms 10328 KB correct
51 Correct 19 ms 16380 KB correct
52 Correct 16 ms 15064 KB correct
53 Correct 15 ms 13868 KB correct
54 Correct 21 ms 17756 KB correct
55 Correct 26 ms 22872 KB correct
56 Correct 28 ms 22868 KB correct
57 Correct 26 ms 22876 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB correct
2 Correct 2 ms 9308 KB correct
3 Correct 204 ms 134628 KB correct
4 Correct 393 ms 250196 KB correct
5 Correct 378 ms 250328 KB correct
6 Correct 378 ms 250192 KB correct
7 Correct 373 ms 250376 KB correct
8 Correct 376 ms 250196 KB correct
9 Correct 382 ms 250280 KB correct
10 Correct 369 ms 250196 KB correct
11 Correct 382 ms 250232 KB correct
12 Correct 383 ms 250136 KB correct
13 Correct 2 ms 9560 KB correct
14 Correct 390 ms 250164 KB correct
15 Correct 368 ms 250152 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB correct
2 Correct 2 ms 9308 KB correct
3 Correct 2 ms 9308 KB correct
4 Correct 2 ms 9308 KB correct
5 Correct 2 ms 9308 KB correct
6 Correct 2 ms 9308 KB correct
7 Correct 2 ms 9304 KB correct
8 Correct 1 ms 9308 KB correct
9 Correct 1 ms 9308 KB correct
10 Correct 2 ms 9308 KB correct
11 Correct 2 ms 9308 KB correct
12 Correct 2 ms 9308 KB correct
13 Correct 2 ms 9304 KB correct
14 Correct 3 ms 9564 KB correct
15 Correct 4 ms 9564 KB correct
16 Correct 3 ms 9564 KB correct
17 Correct 2 ms 9564 KB correct
18 Correct 2 ms 9308 KB correct
19 Correct 3 ms 9564 KB correct
20 Correct 3 ms 9564 KB correct
21 Correct 3 ms 9564 KB correct
22 Correct 2 ms 9304 KB correct
23 Correct 2 ms 9308 KB correct
24 Correct 2 ms 9308 KB correct
25 Correct 2 ms 9308 KB correct
26 Correct 2 ms 9300 KB correct
27 Correct 2 ms 9308 KB correct
28 Correct 2 ms 9328 KB correct
29 Correct 2 ms 9308 KB correct
30 Correct 2 ms 9564 KB correct
31 Correct 2 ms 9568 KB correct
32 Correct 3 ms 9564 KB correct
33 Correct 2 ms 9564 KB correct
34 Correct 54 ms 36512 KB correct
35 Correct 53 ms 35724 KB correct
36 Correct 40 ms 27480 KB correct
37 Correct 8 ms 10332 KB correct
38 Correct 55 ms 36312 KB correct
39 Correct 48 ms 32320 KB correct
40 Correct 39 ms 27472 KB correct
41 Correct 54 ms 36640 KB correct
42 Correct 52 ms 36464 KB correct
43 Correct 21 ms 18012 KB correct
44 Correct 16 ms 14936 KB correct
45 Correct 17 ms 16476 KB correct
46 Correct 14 ms 13828 KB correct
47 Correct 8 ms 10332 KB correct
48 Correct 3 ms 9308 KB correct
49 Correct 4 ms 9592 KB correct
50 Correct 8 ms 10328 KB correct
51 Correct 19 ms 16380 KB correct
52 Correct 16 ms 15064 KB correct
53 Correct 15 ms 13868 KB correct
54 Correct 21 ms 17756 KB correct
55 Correct 26 ms 22872 KB correct
56 Correct 28 ms 22868 KB correct
57 Correct 26 ms 22876 KB correct
58 Correct 2 ms 9308 KB correct
59 Correct 2 ms 9308 KB correct
60 Correct 204 ms 134628 KB correct
61 Correct 393 ms 250196 KB correct
62 Correct 378 ms 250328 KB correct
63 Correct 378 ms 250192 KB correct
64 Correct 373 ms 250376 KB correct
65 Correct 376 ms 250196 KB correct
66 Correct 382 ms 250280 KB correct
67 Correct 369 ms 250196 KB correct
68 Correct 382 ms 250232 KB correct
69 Correct 383 ms 250136 KB correct
70 Correct 2 ms 9560 KB correct
71 Correct 390 ms 250164 KB correct
72 Correct 368 ms 250152 KB correct
73 Correct 2 ms 9308 KB correct
74 Correct 394 ms 250088 KB correct
75 Correct 384 ms 241748 KB correct
76 Correct 131 ms 79188 KB correct
77 Correct 361 ms 249936 KB correct
78 Correct 380 ms 249680 KB correct
79 Correct 372 ms 249428 KB correct
80 Correct 373 ms 242260 KB correct
81 Correct 315 ms 207188 KB correct
82 Correct 363 ms 240832 KB correct
83 Correct 229 ms 128336 KB correct
84 Correct 152 ms 99956 KB correct
85 Correct 122 ms 77904 KB correct
86 Correct 75 ms 43600 KB correct
87 Correct 48 ms 25684 KB correct
88 Correct 38 ms 20076 KB correct
89 Correct 36 ms 19136 KB correct
90 Correct 31 ms 15964 KB correct
91 Correct 14 ms 9564 KB correct
92 Correct 8 ms 9332 KB correct
93 Correct 123 ms 77804 KB correct
94 Correct 75 ms 43860 KB correct
95 Correct 67 ms 38480 KB correct
96 Correct 33 ms 16988 KB correct
97 Correct 39 ms 20056 KB correct
98 Correct 48 ms 25692 KB correct
99 Correct 50 ms 21080 KB correct
100 Correct 19 ms 10328 KB correct
101 Correct 9 ms 9560 KB correct
102 Correct 176 ms 129620 KB correct
103 Correct 172 ms 129620 KB correct
104 Correct 177 ms 128596 KB correct
105 Correct 187 ms 128596 KB correct