Submission #338322

#	Time	Username	Problem	Language	Result	Execution time	Memory
338322		SHZhang	Simurgh (IOI17_simurgh)	C++14	0 / 100	23 ms	4204 KiB

simurgh

#include <vector>
#include <algorithm>
#include <map>
#include "simurgh.h"

using namespace std;

vector<int> graph[505];
bool vis[505];
int depth[505];
int parent[505];
int prtedge[505];
int u[505], v[505];

int n, m;

vector<pair<int, int> > extra_edge;
vector<int> tree_edge;

map<pair<int, int>, int> edge2id;
bool ans[250005];

void dfs(int node, int prt, int dep)
{
    vis[node] = true;
    depth[node] = dep;
    parent[node] = prt;
    for (int i = 0; i < graph[node].size(); i++) {
        int nxt = graph[node][i];
        if (!vis[nxt]) {
            tree_edge.push_back(edge2id[make_pair(node, nxt)]);
            dfs(nxt, node, dep + 1);
        } else if (nxt != prt && depth[nxt] < dep) {
            extra_edge.push_back(make_pair(node, nxt));
        }
    }
}

vector<int> good_edge;
vector<int> unkn_edge[505];

int uf[505];
int fin(int x)
{
    if (uf[x] == x) return x;
    return uf[x] = fin(uf[x]);
}

void un(int x, int y)
{
    x = fin(x); y = fin(y);
    if (x == y) return;
    uf[x] = y;
}

int search(vector<int> ids, int known_amt)
{
    if (ids.empty()) return 0;
    if (known_amt == -1) {
        for (int i = 0; i < n; i++) uf[i] = i;
        int base_val = 0;
        vector<int> query_set;
        for (int i = 0; i < ids.size(); i++) {
            query_set.push_back(ids[i]);
            un(u[ids[i]], v[ids[i]]);
        }
        for (int i = 0; i < tree_edge.size(); i++) {
            int edge = good_edge[i];
            if (fin(u[edge]) == fin(v[edge])) continue;
            un(u[edge], v[edge]);
            query_set.push_back(edge);
            if (ans[edge]) base_val++;
        }
        int query_res = count_common_roads(query_set) - base_val;
        known_amt = query_res;
    }
    if (!known_amt) return 0;
    if (ids.size() == 1) {
        ans[ids[0]] = true; return 1;
    }
    vector<int> left, right;
    for (int i = 0; i < ids.size(); i++) {
        if (i < ids.size() / 2) {
            left.push_back(ids[i]);
        } else {
            right.push_back(ids[i]);
        }
    }
    int left_num = search(left, -1);
    search(right, known_amt - left_num);
    return known_amt;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N; m = U.size();
    for (int i = 0; i < n; i++) prtedge[i] = -1;
    for (int i = 0; i < m; i++) {
        u[i] = U[i]; v[i] = V[i];
        graph[u[i]].push_back(v[i]);
        graph[v[i]].push_back(u[i]);
        edge2id[make_pair(u[i], v[i])] = i;
        edge2id[make_pair(v[i], u[i])] = i;
    }
    dfs(0, -1, 0);
    vector<int> dfs_tree_qry;
    for (int i = 0; i < tree_edge.size(); i++) {
        //fprintf(stderr, "tree %d %d\n", tree_edge[i].first, tree_edge[i].second);
        dfs_tree_qry.push_back(tree_edge[i]);
    }
    int tree_base = count_common_roads(dfs_tree_qry);
    for (int i = 0; i < extra_edge.size(); i++) {
        //fprintf(stderr, "extra %d %d\n", extra_edge[i].first, extra_edge[i].second);
        int curnode = extra_edge[i].first;
        vector<pair<int, int> > query_edge;
        vector<int> query_res;
        //int route_on = 0;
        bool has_zero = false;
        while (curnode != extra_edge[i].second) {
            if (prtedge[curnode] == -1) {
                prtedge[curnode] = i;
                query_edge.push_back(make_pair(curnode, parent[curnode]));
            } else {
                if (!has_zero && !ans[edge2id[make_pair(curnode, parent[curnode])]]) {
                    query_edge.push_back(make_pair(curnode, parent[curnode]));
                    has_zero = true;
                }
            }
            curnode = parent[curnode];
        }
        if (query_edge.size() - (int)has_zero == 0) {
            unkn_edge[extra_edge[i].first].push_back(extra_edge[i].second); continue;
        }
        good_edge.push_back(edge2id[extra_edge[i]]);
        int max_query_res = tree_base;
        for (int j = 0; j < query_edge.size(); j++) {
            vector<int> query_set;
            for (int k = 0; k < n - 1; k++) {
                if (dfs_tree_qry[k] != edge2id[query_edge[j]]) {
                    query_set.push_back(dfs_tree_qry[k]);
                }
            }
            query_set.push_back(edge2id[extra_edge[i]]);
            int cnt = count_common_roads(query_set);
            query_res.push_back(cnt);
            max_query_res = max(max_query_res, cnt);
        }
        for (int j = 0; j < query_edge.size(); j++) {
            if (query_res[j] != max_query_res) {
                //printf("%d %d\n", edge2id[extra_edge[i]], edge2id[query_edge[j]]);
                ans[edge2id[query_edge[j]]] = true;
            }
        }
        //printf("! %d %d\n", edge2id[extra_edge[i]], max_query_res);
        if (tree_base != max_query_res) ans[edge2id[extra_edge[i]]] = true;
    }
    for (int i = 1; i < n; i++) {
        good_edge.push_back(edge2id[make_pair(i, parent[i])]);
        if (prtedge[i] == -1) {
            ans[edge2id[make_pair(i, parent[i])]] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        vector<int> edges;
        for (int j = 0; j < unkn_edge[i].size(); j++) {
            edges.push_back(edge2id[make_pair(i, unkn_edge[i][j])]);
        }
        search(edges, -1);
    }
    vector<int> final_ans;
    for (int i = 0; i < m; i++) {
        if (ans[i]) {
            //fprintf(stderr, "%d\n", i);
            final_ans.push_back(i);
        }
    }
    return final_ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < graph[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int search(std::vector<int>, int)':
simurgh.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0; i < ids.size(); i++) {
      |                         ~~^~~~~~~~~~~~
simurgh.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int i = 0; i < tree_edge.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < ids.size(); i++) {
      |                     ~~^~~~~~~~~~~~
simurgh.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if (i < ids.size() / 2) {
      |             ~~^~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < tree_edge.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < extra_edge.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for (int j = 0; j < query_edge.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int j = 0; j < query_edge.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (int j = 0; j < unkn_edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30