Submission #283350

#	Time	Username	Problem	Language	Result	Execution time	Memory
283350		MKopchev	Simurgh (IOI17_simurgh)	C++14	51 / 100	280 ms	5788 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=500+42;
/*
int count_common_roads(vector<int> r)
{
    for(auto k:r)cout<<k<<" ";

    cout<<" -> ";

    int ret=0;

    for(auto k:r)
        if(k==0||k==1||k==5)ret++;
        //if(k==0||k==1||k==3)ret++;

    //cin>>ret;

    cout<<"ret= "<<ret<<endl;

    while(r.size()!=3)
    {
        while(1);
    }

    return ret;
}
*/
int type[nmax*nmax];//-1-> unknown, 0-> not special, 1-> special

int parent[nmax];
int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

void init(int n_)
{
    for(int i=0;i<n_;i++)
        parent[i]=i;
}

vector< pair<int/*to*/,int/*id*/> > adj[nmax];

int is_forced[nmax*nmax];

vector<int> forced={};

vector< pair<int,int> > edges;

int my_n;

void dumb(int node)
{
    //cout<<"dumb "<<node<<endl;

    //for(int i=0;i<edges.size();i++)cout<<type[i]<<" ";cout<<endl;

    init(my_n);

    vector<int> cur_r=forced,to_solve={};

    for(auto k:forced)
        parent[root(edges[k].first)]=root(edges[k].second);

    int important=-1;

    for(auto k:adj[node])
        if(is_forced[k.second]==0&&type[k.second]!=-1)important=k.second;
        else if(type[k.second]==-1)to_solve.push_back(k.second);

    if(to_solve.size()==0)return;

    vector<int> to_run={};

    if(important!=-1)
    {
        for(int i=0;i<edges.size();i++)
            if(edges[i].first!=node&&edges[i].second!=node&&root(edges[i].first)!=root(edges[i].second))
            {
                parent[root(edges[i].first)]=root(edges[i].second);

                cur_r.push_back(i);
            }

        cur_r.push_back(important);

        int with=count_common_roads(cur_r);

        cur_r.pop_back();

        for(auto k:adj[node])
            if(type[k.second]==-1)
            {
                cur_r.push_back(k.second);

                int cur=count_common_roads(cur_r);

                cur_r.pop_back();

                type[k.second]=cur-with+type[important];

                to_run.push_back(k.first);
            }
    }
    else
    {
        for(int i=0;i<edges.size();i++)
            if(edges[i].first!=node&&edges[i].second!=node&&root(edges[i].first)!=root(edges[i].second))
            {
                parent[root(edges[i].first)]=root(edges[i].second);

                cur_r.push_back(i);

                //cout<<"push "<<i<<endl;
            }
        //cout<<"---"<<endl;

        vector<int> mem={},with={};

        for(auto k:adj[node])
            if(type[k.second]==-1)
            {
                //cout<<"k= "<<k.second<<endl;

                with.push_back(k.second);

                cur_r.push_back(k.second);

                mem.push_back(count_common_roads(cur_r));

                cur_r.pop_back();
            }

        int mini=mem[0],maxi=mem[0];

        for(auto k:mem)
        {
            mini=min(mini,k);
            maxi=max(maxi,k);
        }

        if(mini!=maxi)//mini=maxi => all are equal
        {
            for(int i=0;i<mem.size();i++)
            {
                to_run.push_back(adj[node][i].first);

                type[with[i]]=mem[i]-mini;
            }
        }

    }

    for(auto k:to_run)
        dumb(k);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
    my_n=n;

    for(int i=0;i<u.size();i++)
        edges.push_back({u[i],v[i]});

    memset(type,-1,sizeof(type));

    vector<int> to_test={};

    init(n);

    for(int i=0;i<u.size();i++)
    {
        if(root(u[i])!=root(v[i]))
        {
            to_test.push_back(i);
            parent[root(u[i])]=root(v[i]);
        }

        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
    }

    for(auto cur:to_test)
    {
        init(n);

        for(int i=0;i<u.size()&&root(u[cur])!=root(v[cur]);i++)
            if(root(u[i])!=root(v[i])&&i!=cur)
                parent[root(u[i])]=root(v[i]);

        if(root(u[cur])!=root(v[cur]))
        {
            type[cur]=1;
            forced.push_back(cur);
            is_forced[cur]=1;

            //cout<<"forced "<<cur<<endl;
        }
    }

    for(int i=0;i<n;i++)dumb(i);

    vector<int> ret={};

    for(int i=0;i<edges.size();i++)
        if(type[i]==1)ret.push_back(i);

    return ret;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dumb(int)':
simurgh.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i=0;i<edges.size();i++)
      |                     ~^~~~~~~~~~~~~
simurgh.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int i=0;i<edges.size();i++)
      |                     ~^~~~~~~~~~~~~
simurgh.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for(int i=0;i<mem.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:166:18: 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<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:175:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:191:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(int i=0;i<u.size()&&root(u[cur])!=root(v[cur]);i++)
      |                     ~^~~~~~~~~
simurgh.cpp:209:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~

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