oj.uz

Submission #53700

# Submission time Handle Problem Language Result Execution time Memory
53700 2018-07-01T04:57:12 Z fallingstar Simurgh (IOI17_simurgh) C++14
0 / 100
 3 ms 488 KB 
#include "simurgh.h"

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int N = 240 + 2;

int n, par[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 (auto &e: el)
            if (e.u == i || e.v == i) span.push_back(&e);
        vector<TEdge*> base = SpanningTree(span);
        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;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

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