oj.uz

Submission #397134

# Submission time Handle Problem Language Result Execution time Memory
397134 2021-05-01T14:09:29 Z idk321 Simurgh (IOI17_simurgh) C++11
0 / 100
 1 ms 204 KB 
#include "simurgh.h"


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

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

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

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], in[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;
}

bool vis[N];
void visitAll(int node, int ignore)
{
    vis[node] = true;
    for (auto next : adj[node])
    {
        if (next[1] == ignore || vis[next[0]]) continue;
        visitAll(next[0], ignore);
    }
}


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);
    for (int i = 0; i < m; i++)
    {
        bool ok = true;
        visitAll(0, i);
        for (int j = 0; j < n; j++) ok = ok && vis[j];
        if (!ok) done[i] = true;
    }

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

    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 = -1;
        vector<int> toAdd;
        for (auto next : adj[i])
        {
            if (done[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);
        }
    }



	return res;
}

/*
4 3
0 1
1 2
2 3
0 1 2
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: NO
2 Halted 0 ms 0 KB -