oj.uz

Submission #53730

# Submission time Handle Problem Language Result Execution time Memory
53730 2018-07-01T06:07:52 Z fallingstar Simurgh (IOI17_simurgh) C++14
51 / 100
 359 ms 7136 KB 
#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 (int j = 0; j < n; ++j)
            if (eid[i][j] != -1)
                span.push_back(&el[eid[i][j]]);
        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

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:69:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(base.size() == n - 1);
                ~~~~~~~~~~~~^~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 2 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 520 KB correct
6 Correct 3 ms 524 KB correct
7 Correct 3 ms 580 KB correct
8 Correct 2 ms 584 KB correct
9 Correct 3 ms 588 KB correct
10 Correct 3 ms 592 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 3 ms 732 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 2 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 520 KB correct
6 Correct 3 ms 524 KB correct
7 Correct 3 ms 580 KB correct
8 Correct 2 ms 584 KB correct
9 Correct 3 ms 588 KB correct
10 Correct 3 ms 592 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 3 ms 732 KB correct
14 Correct 6 ms 776 KB correct
15 Correct 7 ms 840 KB correct
16 Correct 8 ms 864 KB correct
17 Correct 7 ms 872 KB correct
18 Correct 4 ms 896 KB correct
19 Correct 5 ms 956 KB correct
20 Correct 5 ms 980 KB correct
21 Correct 5 ms 980 KB correct
22 Correct 5 ms 1016 KB correct
23 Correct 5 ms 1016 KB correct
24 Correct 6 ms 1016 KB correct
25 Correct 4 ms 1016 KB correct
26 Correct 5 ms 1016 KB correct
27 Correct 5 ms 1016 KB correct
28 Correct 4 ms 1016 KB correct
29 Correct 4 ms 1016 KB correct
30 Correct 6 ms 1016 KB correct
31 Correct 6 ms 1016 KB correct
32 Correct 4 ms 1016 KB correct
33 Correct 5 ms 1016 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 2 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 520 KB correct
6 Correct 3 ms 524 KB correct
7 Correct 3 ms 580 KB correct
8 Correct 2 ms 584 KB correct
9 Correct 3 ms 588 KB correct
10 Correct 3 ms 592 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 3 ms 732 KB correct
14 Correct 6 ms 776 KB correct
15 Correct 7 ms 840 KB correct
16 Correct 8 ms 864 KB correct
17 Correct 7 ms 872 KB correct
18 Correct 4 ms 896 KB correct
19 Correct 5 ms 956 KB correct
20 Correct 5 ms 980 KB correct
21 Correct 5 ms 980 KB correct
22 Correct 5 ms 1016 KB correct
23 Correct 5 ms 1016 KB correct
24 Correct 6 ms 1016 KB correct
25 Correct 4 ms 1016 KB correct
26 Correct 5 ms 1016 KB correct
27 Correct 5 ms 1016 KB correct
28 Correct 4 ms 1016 KB correct
29 Correct 4 ms 1016 KB correct
30 Correct 6 ms 1016 KB correct
31 Correct 6 ms 1016 KB correct
32 Correct 4 ms 1016 KB correct
33 Correct 5 ms 1016 KB correct
34 Correct 359 ms 2788 KB correct
35 Correct 305 ms 2916 KB correct
36 Correct 223 ms 2916 KB correct
37 Correct 44 ms 2916 KB correct
38 Correct 328 ms 3404 KB correct
39 Correct 293 ms 3452 KB correct
40 Correct 225 ms 3460 KB correct
41 Correct 324 ms 3916 KB correct
42 Correct 308 ms 4104 KB correct
43 Correct 155 ms 4104 KB correct
44 Correct 138 ms 4104 KB correct
45 Correct 154 ms 4104 KB correct
46 Correct 125 ms 4104 KB correct
47 Correct 70 ms 4104 KB correct
48 Correct 33 ms 4104 KB correct
49 Correct 42 ms 4104 KB correct
50 Correct 74 ms 4104 KB correct
51 Correct 155 ms 4104 KB correct
52 Correct 134 ms 4104 KB correct
53 Correct 126 ms 4104 KB correct
54 Correct 167 ms 4104 KB correct
55 Correct 161 ms 4212 KB correct
56 Correct 147 ms 4316 KB correct
57 Correct 175 ms 4420 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4420 KB correct
2 Correct 2 ms 4420 KB correct
3 Runtime error 23 ms 7136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 2 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 520 KB correct
6 Correct 3 ms 524 KB correct
7 Correct 3 ms 580 KB correct
8 Correct 2 ms 584 KB correct
9 Correct 3 ms 588 KB correct
10 Correct 3 ms 592 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 3 ms 732 KB correct
14 Correct 6 ms 776 KB correct
15 Correct 7 ms 840 KB correct
16 Correct 8 ms 864 KB correct
17 Correct 7 ms 872 KB correct
18 Correct 4 ms 896 KB correct
19 Correct 5 ms 956 KB correct
20 Correct 5 ms 980 KB correct
21 Correct 5 ms 980 KB correct
22 Correct 5 ms 1016 KB correct
23 Correct 5 ms 1016 KB correct
24 Correct 6 ms 1016 KB correct
25 Correct 4 ms 1016 KB correct
26 Correct 5 ms 1016 KB correct
27 Correct 5 ms 1016 KB correct
28 Correct 4 ms 1016 KB correct
29 Correct 4 ms 1016 KB correct
30 Correct 6 ms 1016 KB correct
31 Correct 6 ms 1016 KB correct
32 Correct 4 ms 1016 KB correct
33 Correct 5 ms 1016 KB correct
34 Correct 359 ms 2788 KB correct
35 Correct 305 ms 2916 KB correct
36 Correct 223 ms 2916 KB correct
37 Correct 44 ms 2916 KB correct
38 Correct 328 ms 3404 KB correct
39 Correct 293 ms 3452 KB correct
40 Correct 225 ms 3460 KB correct
41 Correct 324 ms 3916 KB correct
42 Correct 308 ms 4104 KB correct
43 Correct 155 ms 4104 KB correct
44 Correct 138 ms 4104 KB correct
45 Correct 154 ms 4104 KB correct
46 Correct 125 ms 4104 KB correct
47 Correct 70 ms 4104 KB correct
48 Correct 33 ms 4104 KB correct
49 Correct 42 ms 4104 KB correct
50 Correct 74 ms 4104 KB correct
51 Correct 155 ms 4104 KB correct
52 Correct 134 ms 4104 KB correct
53 Correct 126 ms 4104 KB correct
54 Correct 167 ms 4104 KB correct
55 Correct 161 ms 4212 KB correct
56 Correct 147 ms 4316 KB correct
57 Correct 175 ms 4420 KB correct
58 Correct 2 ms 4420 KB correct
59 Correct 2 ms 4420 KB correct
60 Runtime error 23 ms 7136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Halted 0 ms 0 KB -