Submission #767165

#	Time	Username	Problem	Language	Result	Execution time	Memory
767165		danikoynov	Simurgh (IOI17_simurgh)	C++14	30 / 100	136 ms	49456 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);
        }
    }
}
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
    int m = u.size();
    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);
        }
    }

    for (int i = 0; i < m; i ++)
        if (!visit[i])
    {
        gold.push_back(i);
        span.push_back(i);
        is_gold[i] = 1;
    }

        for (vector < int > cycle : cycles)
        {
            for (int i = 0; i < n; i ++)
                used[i] = 0;
            for (int i = 0; i < cycle.size(); i ++)
            {
                int edge = cycle[i];
            used[v[edge]] = used[u[edge]] = 2;
            }

            tree.clear();
            for (int i = 0; i < n; i ++)
            {
                if (used[i] == 2)
                    trav(i);
            }
            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;
                }
            }
        }

        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 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:132:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int i = 0; i < cycle.size(); i ++)
      |                             ~~^~~~~~~~~~~~~~
simurgh.cpp:146:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for (int i = 0; i < cycle.size(); i ++)
      |                             ~~^~~~~~~~~~~~~~
simurgh.cpp:149:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |                 for (int j = 0; j < cycle.size(); j ++)
      |                                 ~~^~~~~~~~~~~~~~
simurgh.cpp:166:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                 for (int i = 0; i < cycle.size(); i ++)
      |                                 ~~^~~~~~~~~~~~~~

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