Submission #1100053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100053		MMihalev	Simurgh (IOI17_simurgh)	C++14	0 / 100	69 ms	3576 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;
int q;
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);q++;

        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);q++;
            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);q++;

                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(q>10000)while(1);

    return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto [v,edge]:g[u])
      |              ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto [v,edge]:g[u])
      |                  ^
simurgh.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [v,edge]:g[u])
      |                  ^
simurgh.cpp:94:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |             for(auto [v,edge]:g[u])
      |                      ^

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