oj.uz

Submission #397150

# Submission time Handle Problem Language Result Execution time Memory
397150 2021-05-01T14:55:36 Z idk321 Simurgh (IOI17_simurgh) C++11
30 / 100
 248 ms 4128 KB 
#include "simurgh.h"


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 30000;
const int M = 30000;
vector<array<int, 2>> adj[N];
int n;
int m;

int in[N];
int up[N];
int timer;
bool done[M];
bool inRes[M];

void bridges(int node, int par, int pEdge)
{
    in[node] = ++timer;
    up[node] = in[node];

    for (auto next : adj[node])
    {
        if (next[0] == par) continue;
        if (in[next[0]] == 0)
        {
            bridges(next[0], node, next[1]);
            up[node] = min(up[node], up[next[0]]);
        } else
        {
            up[node] = min(up[node], up[next[0]]);
        }
    }

    if (par != -1 && up[node] == in[node])
    {
        done[pEdge] = true;
    }
}

int p[N];

int getRoot(int a)
{
    if (p[a] == a) return a;
    p[a] = getRoot(p[a]);
    return p[a];
}

void join(int a, int b)
{
    a = getRoot(a);
    b = getRoot(b);
    p[b] = a;
}


std::vector<int> find_roads(int XD, std::vector<int> u, std::vector<int> v) {
    n = XD;
    m = u.size();
    for (int i = 0; i < m; i++)
    {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }

    bridges(0, -1, -1);

    vector<int> res;
    for (int i = 0; i < m; i++) if (done[i])
    {
         res.push_back(i);
         inRes[i] = true;
    }


    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            p[j] = j;
        }

        vector<int> gold;
        for (int i = 0; i < m; i++)
        {
            if (done[i])
            {
                 join(u[i], v[i]);
                 gold.push_back(i);
            }
        }
        for (int j = 0; j < m; j++)
        {
            if (u[j] != i && v[j] != i && getRoot(u[j]) != getRoot(v[j]))
            {
                join(u[j], v[j]);
                gold.push_back(j);
            }
        }

        int best = 0;

        for (auto next : adj[i])
        {
            if (inRes[next[1]] && !done[next[1]] && getRoot(i) != getRoot(next[0]))
            {
                gold.push_back(next[1]);
                //cout << gold.size() << endl;
                int quer = count_common_roads(gold);
                gold.pop_back();
                best = quer;
                break;
            }
        }

        vector<int> toAdd;
        for (auto next : adj[i])
        {
            if (inRes[next[1]]) continue;
            if (getRoot(i) != getRoot(next[0]))
            {
                gold.push_back(next[1]);
                //cout << gold.size() << endl;
                int quer = count_common_roads(gold);
                gold.pop_back();
                if (quer == best)
                {
                    toAdd.push_back(next[1]);
                } else if (quer > best)
                {
                    best = quer;
                    toAdd.clear();
                    toAdd.push_back(next[1]);
                }
            }
        }

        for (int edge : toAdd)
        {
            res.push_back(edge);
            inRes[edge] = true;
        }
    }



    return res;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB correct
2 Correct 1 ms 972 KB correct
3 Correct 1 ms 972 KB correct
4 Correct 1 ms 972 KB correct
5 Correct 1 ms 972 KB correct
6 Correct 1 ms 972 KB correct
7 Correct 1 ms 972 KB correct
8 Correct 1 ms 972 KB correct
9 Correct 1 ms 972 KB correct
10 Correct 1 ms 972 KB correct
11 Correct 1 ms 972 KB correct
12 Correct 2 ms 972 KB correct
13 Correct 1 ms 972 KB correct
14 Correct 5 ms 972 KB correct
15 Correct 5 ms 972 KB correct
16 Correct 5 ms 972 KB correct
17 Correct 4 ms 972 KB correct
18 Correct 2 ms 972 KB correct
19 Correct 5 ms 1080 KB correct
20 Correct 4 ms 972 KB correct
21 Correct 4 ms 972 KB correct
22 Correct 4 ms 972 KB correct
23 Correct 3 ms 1056 KB correct
24 Correct 3 ms 972 KB correct
25 Correct 2 ms 972 KB correct
26 Correct 3 ms 972 KB correct
27 Correct 3 ms 972 KB correct
28 Correct 2 ms 972 KB correct
29 Correct 2 ms 972 KB correct
30 Correct 3 ms 972 KB correct
31 Correct 3 ms 972 KB correct
32 Correct 3 ms 972 KB correct
33 Correct 3 ms 972 KB correct
34 Incorrect 248 ms 2080 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB correct
2 Correct 1 ms 972 KB correct
3 Incorrect 85 ms 4128 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB correct
2 Correct 1 ms 972 KB correct
3 Correct 1 ms 972 KB correct
4 Correct 1 ms 972 KB correct
5 Correct 1 ms 972 KB correct
6 Correct 1 ms 972 KB correct
7 Correct 1 ms 972 KB correct
8 Correct 1 ms 972 KB correct
9 Correct 1 ms 972 KB correct
10 Correct 1 ms 972 KB correct
11 Correct 1 ms 972 KB correct
12 Correct 2 ms 972 KB correct
13 Correct 1 ms 972 KB correct
14 Correct 5 ms 972 KB correct
15 Correct 5 ms 972 KB correct
16 Correct 5 ms 972 KB correct
17 Correct 4 ms 972 KB correct
18 Correct 2 ms 972 KB correct
19 Correct 5 ms 1080 KB correct
20 Correct 4 ms 972 KB correct
21 Correct 4 ms 972 KB correct
22 Correct 4 ms 972 KB correct
23 Correct 3 ms 1056 KB correct
24 Correct 3 ms 972 KB correct
25 Correct 2 ms 972 KB correct
26 Correct 3 ms 972 KB correct
27 Correct 3 ms 972 KB correct
28 Correct 2 ms 972 KB correct
29 Correct 2 ms 972 KB correct
30 Correct 3 ms 972 KB correct
31 Correct 3 ms 972 KB correct
32 Correct 3 ms 972 KB correct
33 Correct 3 ms 972 KB correct
34 Incorrect 248 ms 2080 KB WA in grader: NO
35 Halted 0 ms 0 KB -