Submission #767204

#	Time	Username	Problem	Language	Result	Execution time	Memory
767204		danikoynov	Simurgh (IOI17_simurgh)	C++14	100 / 100	425 ms	95656 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
struct disjoint_set_union
{
    int par[maxn];

    disjoint_set_union() {};

    disjoint_set_union(int n)
    {
        for (int i = 0; i < n; i ++)
            par[i] = i;
    }

    int find_leader(int v)
    {
        if (v == par[v])
            return v;
        return (par[v] = find_leader(par[v]));
    }

    bool is_connected(int v, int u)
    {
        return find_leader(v) == find_leader(u);
    }

    void unite(int v, int u)
    {
        v = find_leader(v);
        u = find_leader(u);
        if (v == u)
            return;
        par[v] = u;
    }
};

int is_bridge[maxn * maxn];
int direction[maxn * maxn];
vector < pair < int, int > > adj[maxn];
int par[maxn], par_idx[maxn], used[maxn];
int depth[maxn];
void dfs(int v)
{
    used[v] = 1;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == par[v])
            continue;
        if (!used[nb.first])
        {
            par_idx[nb.first] = nb.second;
            par[nb.first] = v;
            direction[nb.second] = 1;
            depth[nb.first] = depth[v] + 1;
            dfs(nb.first);
        }
        else
        {
            direction[nb.second] = -1;
        }
    }
}

vector < vector < int > > cycles;
vector < int > gold;
int visit[maxn * maxn], is_gold[maxn * maxn];
vector < int > span;
vector < int > tree;
void trav(int v)
{
    for (pair < int, int > nb : adj[v])
    {
        if (used[nb.first] == 0)
        {
            used[nb.first] = 1;
            tree.push_back(nb.second);
            trav(nb.first);
        }
    }
}


int N, M;
pair < int, int > ed[maxn * maxn];
vector < int > out[maxn];
int delta_gold(vector < int > edges)
{
    vector < int > res;
    res = edges;
    disjoint_set_union dsu(N);
    for (int i = 0; i < edges.size(); i ++)
        dsu.unite(ed[edges[i]].first, ed[edges[i]].second);


    int new_gold = 0;
    for (int i = 0; i < edges.size(); i ++)
        if (is_gold[edges[i]] == 1)
            new_gold --;
    for (int i = 0; i < span.size(); i ++)
    {
        int idx = span[i];
        int v = ed[idx].first, u = ed[idx].second;
        if (!dsu.is_connected(v, u))
        {
            dsu.unite(v, u);
            if (is_gold[idx] == 1)
            {
                ///cout << "--- " << v << " " << u << endl;
                new_gold --;
            }
            res.push_back(idx);
        }
    }
    ///cout << "delta" << endl;
    for (int i = 0; i < res.size(); i ++)
    {
        int idx = res[i];
        ///cout << ed[idx].first << " -- " << ed[idx].second << endl;
    }
    ///cout << new_gold << endl;
    new_gold = new_gold + count_common_roads(res);
    return new_gold;
}

int deg[maxn];
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
    int m = u.size();
    N = n;
    M = m;
    for (int i = 0; i < m; i ++)
    {
        ed[i] = {u[i], v[i]};
    }
    for (int i = 0; i < m; i ++)
    {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }

    par[0] = -1;
    par_idx[0] = -1;
    dfs(0);

    for (int i = 0; i < m; i ++)
    {
        int V = u[i], U = v[i];
        if (direction[i] == -1)
        {
            if (depth[V] < depth[U])
                swap(V, U);
            vector < int > cycle;
            int cur = V;
            while(cur != U)
            {
                visit[par_idx[cur]] = 1;
                cycle.push_back(par_idx[cur]);
                cur = par[cur];

            }
            visit[i] = 1;
            cycle.push_back(i);
            cycles.push_back(cycle);
        }
    }
    /**cout << "--------------" << endl;
    for (int i = 0; i < m; i ++)
    {
        if (direction[i] == 1)
            cout << u[i] << " : " << v[i] << endl;
    }
    cout << "-------------" << endl;*/
    for (int i = 0; i < m; i ++)
    {
        if (!visit[i])
        {
            gold.push_back(i);
            span.push_back(i);
            is_gold[i] = 1;
        }
        else
        {
            if (direction[i] == 1)
                span.push_back(i);
        }
    }

    for (vector < int > cycle : cycles)
    {
        for (int i = 0; i < n; i ++)
            used[i] = 0;

        bool need = false;
        int mx = -1;
        for (int i = 0; i < cycle.size() - 1; i ++)
        {
            int edge = cycle[i];
            if (is_gold[edge] == 0)
                need = true;
            else
                mx = i;
            used[v[edge]] = used[u[edge]] = 2;
        }

        if (!need)
            continue;


        tree.clear();
        for (int i = 0; i < n; i ++)
        {
            if (used[i] == 2)
                trav(i);
        }

        if (mx == -1)
        {

            vector < int > values;
            int max_val = -1, min_val = 1e9;
            for (int i = 0; i < cycle.size(); i ++)
            {
                vector < int > res = tree;
                for (int j = 0; j < cycle.size(); j ++)
                {
                    if (i != j)
                        res.push_back(cycle[j]);
                }
                values.push_back(count_common_roads(res));
                max_val = max(max_val, values.back());
                min_val = min(min_val, values.back());
            }

            if (max_val == min_val)
            {
                for (int idx : cycle)
                    is_gold[idx] = -1;
            }
            else
            {
                for (int i = 0; i < cycle.size(); i ++)
                {
                    if (values[i] == min_val)
                        is_gold[cycle[i]] = 1;
                    else
                        is_gold[cycle[i]] = -1;
                }
            }
        }
        else
        {

                        /**cout << "base" << endl;
            for (int i = 0; i < cycle.size(); i ++)
            {
                int idx = cycle[i];
                cout << u[idx] << " " << v[idx] << endl;
            }*/

            int max_val = 0, min_val = 1e9;
            vector < int > res = tree;
            ///cout << res.size() << " : " << cycle.size() << " " << mx << endl;
            for (int i = 0; i < cycle.size(); i ++)
                if (i != mx)
                    res.push_back(cycle[i]);

            int val = count_common_roads(res);
            if (is_gold[cycle[mx]] == 1)
            {
                min_val = val;
                max_val = val + 1;
            }
            else
            {
                min_val = val - 1;
                max_val = val;
            }

            for (int i = 0; i < cycle.size() - 1; i ++)
            {
                if (is_gold[cycle[i]] == 0)
                {
                    res = tree;
                    for (int j = 0; j < cycle.size(); j ++)
                        if (j != i)
                            res.push_back(cycle[j]);

                    val = count_common_roads(res);
                    if (val == max_val)
                        is_gold[cycle[i]] = -1;
                    else
                        is_gold[cycle[i]] = 1;
                }
            }
        }
    }

    /**cout << "Span" << endl;
    for (int i = 0; i < span.size(); i ++)
    {
        int idx = span[i];
        cout << u[idx] << " : " << v[idx] << " " << is_gold[idx] << endl;
    }*/
    queue < int > q;
    for (int i = 0; i < n; i ++)
    {

        for (int j = 0; j < m; j ++)
        {
            if (v[j] == i || u[j] == i)
                out[i].push_back(j);
        }

        deg[i] = delta_gold(out[i]);
        if (deg[i] == 1)
            q.push(i);
    }

    //cout << delta_gold(out[1]) << endl;
    //exit(0);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        if (deg[cur] == 0)
            continue;
        int l = 0, r = out[cur].size() - 1;
        while(l <= r)
        {
            int m = (l + r) / 2;
            vector < int > st;
            for (int i = 0; i <= m; i ++)
                st.push_back(out[cur][i]);
            if (delta_gold(st) > 0)
                r = m - 1;
            else
                l = m + 1;
        }
        is_gold[out[cur][l]] = 1;
        int oth = u[out[cur][l]];
        if (oth == cur)
            oth = v[out[cur][l]];
        deg[oth] --;
        deg[cur] --;
        if (deg[oth] == 1)
            q.push(oth);
    }

    vector < int > ans;
    for (int i = 0; i < m; i ++)
        if (is_gold[i] == 1)
            ans.push_back(i);
    return ans;

}

Compilation message (stderr)

simurgh.cpp: In function 'int delta_gold(std::vector<int>)':
simurgh.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < edges.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
simurgh.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < edges.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
simurgh.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 0; i < span.size(); i ++)
      |                     ~~^~~~~~~~~~~~~
simurgh.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 0; i < res.size(); i ++)
      |                     ~~^~~~~~~~~~~~
simurgh.cpp:121:13: warning: unused variable 'idx' [-Wunused-variable]
  121 |         int idx = res[i];
      |             ^~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:199:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |         for (int i = 0; i < cycle.size() - 1; i ++)
      |                         ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:225:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |             for (int i = 0; i < cycle.size(); i ++)
      |                             ~~^~~~~~~~~~~~~~
simurgh.cpp:228:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |                 for (int j = 0; j < cycle.size(); j ++)
      |                                 ~~^~~~~~~~~~~~~~
simurgh.cpp:245:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |                 for (int i = 0; i < cycle.size(); i ++)
      |                                 ~~^~~~~~~~~~~~~~
simurgh.cpp:267:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |             for (int i = 0; i < cycle.size(); i ++)
      |                             ~~^~~~~~~~~~~~~~
simurgh.cpp:283:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  283 |             for (int i = 0; i < cycle.size() - 1; i ++)
      |                             ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:288:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |                     for (int j = 0; j < cycle.size(); j ++)
      |                                     ~~^~~~~~~~~~~~~~
simurgh.cpp:264:30: warning: variable 'min_val' set but not used [-Wunused-but-set-variable]
  264 |             int max_val = 0, min_val = 1e9;
      |                              ^~~~~~~

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