Submission #499600

#	Time	Username	Problem	Language	Result	Execution time	Memory
499600		CatalinT	Simurgh (IOI17_simurgh)	C++17	51 / 100	146 ms	4996 KiB

simurgh

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
 
using namespace std;

#include "simurgh.h"

using int64 = long long;

int N, M;
vector<vector<int>> eidx;
vector<vector<int>> adj;
vector<int> par;
vector<int> depth;
vector<char> used;

vector<int> status;

vector<int> tree_idx;
vector<int> back_idx;
vector<int> all_idx;

vector<char> added;

int get(int u, int v) {
    assert(eidx[u][v] != -1);
    return eidx[u][v];
}

void dfs(int n, int p) {
    //cerr << n << " " << p << "\n";
    used[n] = true;
    for (auto v : adj[n]) {
        if (v != p) {
            int e = get(n, v);
           
            if (!used[v]) {
                // Forward edge
                par[v] = n;
                depth[v] = depth[n] + 1;
                tree_idx.push_back(e);
                all_idx.push_back(e);
                dfs(v, n);
            } else if (!added[e]) {
                added[e] = true;
                back_idx.push_back(e);
                all_idx.push_back(e);
            }
        }
    }
}

vector<int> get_cycle(int u, int v) {
    vector<int> edges;
    
    auto go_up = [&] (int & el) {
        edges.push_back(get(el, par[el]));
        el = par[el];
    };

    while(depth[u] > depth[v]) {
        go_up(u);
    }
    while(depth[u] < depth[v]) {
        go_up(v);
    }
    while(u != v) {
        go_up(u);
        go_up(v);
    }

    return edges;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    auto edge_str = [&](int e) {
        return to_string(u[e]) + " - " + to_string(v[e]) + " idx: " + to_string(e);
    };

    N = n;
    M = u.size();

    adj.resize(N, vector<int>{});
    eidx.resize(N, vector<int>(N, -1));
    par.resize(N, -1);
    used.resize(N, 0);
    depth.resize(N, 0);
    
    status.resize(M, -1);
    added.resize(M, 0);

    for (int i = 0; i < M; i++) {
        eidx[ u[i] ][ v[i] ] = eidx[ v[i] ][ u[i] ] = i;
        adj[ u[i] ].push_back( v[i] );
        adj[ v[i] ].push_back( u[i] );
    }

    // 1. Find DFS tree
    dfs(0, 0);

    assert(tree_idx.size() == N - 1);
    assert(tree_idx.size() + back_idx.size() == M);
    assert(all_idx.size() == M);

    // cerr << "tree edges:\n";
    for (auto e : tree_idx) {
        // cerr << edge_str(e) << "\n";
        assert(status[e] == -1);
    }

    // 50 points

    int tree_ans = count_common_roads(tree_idx);
    // cerr << "tree_ans: " << tree_ans << "\n";

    for (auto e : back_idx) {
        // get cycle
        auto cycle = get_cycle(u[e], v[e]);
        int unknown = 0;
        for (auto c : cycle)
            unknown += (status[c] == -1);

        // cerr << "Back edge: " << edge_str(e) << "\n";
        // cerr << "cycle\n";
        // for (auto c : cycle) {
        //     cerr << edge_str(c) << "\n";
        // }

        auto replace = [] (int e, int c, vector<int>& query) {
            auto p = find(query.begin(), query.end(), c);
            assert(p != query.end());
            *p = e;
        };

        auto replace_and_query = [&] (int e, int c) {
            auto query = tree_idx;
            replace(e, c, query);
            return count_common_roads(query) - tree_ans;
        };

        if (!unknown) { // all is known
            // cerr << "all known\n";
            // Just 1 query needed
            status[e] = replace_and_query(e, cycle[0]) + status[cycle[0]];
        } else if (unknown < cycle.size()) { // at least one is known
            // cerr << "at least one is known\n";
            // <= C++14
            int cand = -1;
            for (auto c : cycle) {
                if (status[c] != -1) {
                    cand = c;
                    break;
                }
            }

            status[e] = replace_and_query(e, cand) + status[cand];

            // use this to find the unknowns
            for (auto c : cycle) {
                if (status[c] == -1) {
                    status[c] = -replace_and_query(e, c) + status[e];
                }
            }
        } else { // all is unknown
            // cerr << "all is unknown\n";

            int neg = 0;
            int pos = 0;

            for (auto c : cycle) {
                status[c] = replace_and_query(e, c);
                // cerr << edge_str(c) << " delta: " << status[c] << "\n";
                neg += (status[c] < 0);
                pos += (status[c] > 0);
            }

            if (!pos && !neg) {
                // cerr << "nothing is different\n";
                assert (!pos);
                assert (!neg);
                for (auto c : cycle) {
                    status[c] = 0;
                }
                status[e] = 0;
            } else {
                assert(!pos || !neg);
                if (pos) {
                    for (auto c : cycle) {
                        status[c] = 1 - status[c];
                    }
                    status[e] = 1;
                    // cerr << "positive e\n";
                } else {
                    for (auto c : cycle) {
                        status[c] = -status[c];
                    }
                    status[e] = 0;
                    // cerr << "negative e\n";
                }

                // cerr << "find out\n";
                // for (auto c : cycle) {
                //     cerr << edge_str(c) << " -> " << status[c] << "\n";
                // }
                // cerr << "\n";
            }
        }
    }

    vector<int> res;

    int rem_unknown = 0;
    int rem_good = 0;

    for (auto e : all_idx) {
        if (status[e] == -1) {
            rem_unknown++;
            res.push_back(e);
        } else if (status[e] == 1) {
            rem_good++;
            res.push_back(e);
        }
    }

    assert(rem_good + rem_unknown == N - 1);

    return res;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from simurgh.cpp:16:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:118:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |     assert(tree_idx.size() == N - 1);
      |            ~~~~~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:119:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |     assert(tree_idx.size() + back_idx.size() == M);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
simurgh.cpp:120:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |     assert(all_idx.size() == M);
      |            ~~~~~~~~~~~~~~~^~~~
simurgh.cpp:162:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         } else if (unknown < cycle.size()) { // at least one is known
      |                    ~~~~~~~~^~~~~~~~~~~~~~
simurgh.cpp:93:10: warning: variable 'edge_str' set but not used [-Wunused-but-set-variable]
   93 |     auto edge_str = [&](int e) {
      |          ^~~~~~~~

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