Submission #1100050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100050		MMihalev	Simurgh (IOI17_simurgh)	C++14	0 / 100	69 ms	3564 KiB

simurgh

#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include "simurgh.h"
using namespace std;
const int MAX_N=5e2+3;
const int MAX_M=125000;
int n,m;
vector<pair<int,int>>g[MAX_N];
vector<int>edges;
bool used[MAX_N];

bool stat[MAX_M];

void reset()
{
    edges.clear();
    for(int i=0;i<n;i++)
    {
        used[i]=0;
    }
}
void dfs(int u)
{
    used[u]=1;
    for(auto [v,edge]:g[u])
    {
        if(used[v])continue;
        edges.push_back(edge);
        dfs(v);
    }
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
    n=N;
    m=u.size();
    vector<int>ans;
    for(int i=0;i<m;i++)
    {
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }

    for(int u=0;u<n;u++)
    {
        vector<int>marked;
        bool changed=0;

        for(auto [v,edge]:g[u])
        {
            if(v<u)continue;
            reset();
            used[u]=1;
            dfs(v);
            edges.push_back(edge);
            marked.push_back(edge);
            break;
        }

        if(marked.size()==0)continue;

        int ma=count_common_roads(edges);

        for(auto [v,edge]:g[u])
        {
            if(v<u)continue;
            if(edges.back()==edge)continue;

            edges.pop_back();
            edges.push_back(edge);
            int cur=count_common_roads(edges);
            if(cur>ma)
            {
                marked.clear();
                changed=1;
                marked.push_back(edge);
                ma=cur;
            }
            else if(cur==ma)
            {
                marked.push_back(edge);
            }
        }

        if(changed)
        {
            for(int edge:marked)stat[edge]=1;
        }
        else
        {
            int forsure=-1;
            for(auto [v,edge]:g[u])
            {
                if(stat[edge])forsure=edge;
            }

            if(forsure==-1)
            {
                for(int edge:marked)stat[edge]=1;
            }
            else
            {
                edges.pop_back();
                edges.push_back(forsure);
                int forsuremax=count_common_roads(edges);

                if(forsuremax==ma)for(int edge:marked)stat[edge]=1;
            }
        }
    }

    for(int i=0;i<m;i++)
    {
        if(stat[i])ans.push_back(i);
    }

    if(ans.size()!=n-1)while(1);

    return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto [v,edge]:g[u])
      |              ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         for(auto [v,edge]:g[u])
      |                  ^
simurgh.cpp:65:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         for(auto [v,edge]:g[u])
      |                  ^
simurgh.cpp:93:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |             for(auto [v,edge]:g[u])
      |                      ^
simurgh.cpp:118:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |     if(ans.size()!=n-1)while(1);
      |        ~~~~~~~~~~^~~~~

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