Submission #499604

#	Time	Username	Problem	Language	Result	Execution time	Memory
499604		CatalinT	Simurgh (IOI17_simurgh)	C++17	100 / 100	566 ms	7880 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, Q;
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> is_tree;
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);
                is_tree[e] = 1;
                dfs(v, n);
            } else if (!added[e]) {
                added[e] = true;
                back_idx.push_back(e);
                all_idx.push_back(e);
            }
        }
    }
}

void redo_par(int n, int p) {
    for (auto v : adj[n]) {
        if (v != p) {
            int e = get(n, v);
            if (!is_tree[e])
                continue;
            par[v] = n;
            redo_par(v, n);
        }
    }
}

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);
    
    is_tree.resize(M, 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";

    // 2. Find status of all edges in tree_idx

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

    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_and_query = [&] (int e, int c) {
            auto query = tree_idx;
            replace(e, c, query);
            Q++;
            return count_common_roads(query) - tree_ans;
        };  

        if (!unknown) { // all is known
            // Just 1 query needed but useless since we want to find out tree_idx
            //status[e] = replace_and_query(e, cycle[0]) + status[cycle[0]];
            continue;
        } 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";
            }
        }
    }

    for (auto e : tree_idx) {
        if (status[e] == -1) {
            status[e] = 1;
        }
    }

    cerr << "first phase Q: " << Q << "\n";

    // 3. Binary search to find remaining edges

    vector<int> end_point(M);

    for (int n = 0; n < N; n++) {
        redo_par(n, n);

        vector<int> cand_idx;
        
        for (int j = 0; j < N; j++) {
            if (eidx[n][j] == -1)
                continue; 
            assert(j != n);
            int e = get(n, j);
            if (status[e] == -1 && !is_tree[e]) {
                cand_idx.push_back(e);
                end_point[e] = j;
            } 
        }
        if (!cand_idx.size())
            continue;

        // auto multi_query = [&](const vector<int> & qset) {
        //     auto query = tree_idx;
        //     int delta = 0;
        //     for (auto e : qset) {
        //         int re = get(end_point[e], par[end_point[e]]);
        //         assert(status[re] != -1);
        //         delta -= status[re];
        //         replace(e, re, query);
        //     }
        //     return count_common_roads(query) - (tree_ans + delta);
        // };

        auto multi_query = [&](int l, int r) {
            auto query = tree_idx;
            int delta = 0;
            for (int i = l; i <= r; i++) {
                auto e = cand_idx[i];

                int re = get(end_point[e], par[end_point[e]]);
                assert(status[re] != -1);
                delta -= status[re];
                replace(e, re, query);
            }
            Q++;
            return count_common_roads(query) - (tree_ans + delta);
        };


        auto full_ans = multi_query(0, cand_idx.size() - 1);
    
        function<void(int, int, int)> Rec = [&] (int l, int r, int tot) {
            int m = (l + r) >> 1;
            int sz = (r - l + 1);

            int left_ans = multi_query(l, m);

            int right_ans = tot - left_ans;

            auto Continue = [&] (int l1, int r1, int ans) {
                int sz = r1 - l1 + 1;

                if (!ans) {
                    for (int i = l1; i <= r1; i++) {
                        status[cand_idx[i]] = 0;
                    }
                    return false;
                } else if (ans == sz) {
                    for (int i = l1; i <= r1; i++) {
                        status[cand_idx[i]] = 1;
                    }
                    return false;
                } else {
                    return true;
                }
            };

            if (Continue(l, m, left_ans)) {
                Rec(l, m, left_ans);
            }
            if (Continue(m + 1, r, right_ans)) {
                Rec(m + 1, r, right_ans);
            }
        };

        // REDO
        if (!full_ans) {
            for (auto e : cand_idx)
                status[e] = 0;
        } else if (full_ans == cand_idx.size()) {
            for (auto e : cand_idx)
                status[e] = 1;
        } else {
            Rec(0, cand_idx.size() - 1, full_ans);
        }
    }

    cerr << "second phase Q: " << Q << "\n";

    vector<int> res;

    for (auto e : all_idx) {
        if (status[e] == 1) {
            res.push_back(e);
        }
    }

    assert(res.size() == 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:133:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  133 |     assert(tree_idx.size() == N - 1);
      |            ~~~~~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:134:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |     assert(tree_idx.size() + back_idx.size() == M);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
simurgh.cpp:135:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |     assert(all_idx.size() == M);
      |            ~~~~~~~~~~~~~~~^~~~
simurgh.cpp:180:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         } else if (unknown < cycle.size()) { // at least one is known
      |                    ~~~~~~~~^~~~~~~~~~~~~~
simurgh.cpp: In lambda function:
simurgh.cpp:307:17: warning: unused variable 'sz' [-Wunused-variable]
  307 |             int sz = (r - l + 1);
      |                 ^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:343:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  343 |         } else if (full_ans == cand_idx.size()) {
      |                    ~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from simurgh.cpp:16:
simurgh.cpp:361:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  361 |     assert(res.size() == N - 1);
      |            ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:107:10: warning: variable 'edge_str' set but not used [-Wunused-but-set-variable]
  107 |     auto edge_str = [&](int e) {
      |          ^~~~~~~~

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