Submission #429603

#	Time	Username	Problem	Language	Result	Execution time	Memory
429603		inwbear	Simurgh (IOI17_simurgh)	C++14	30 / 100	192 ms	1680 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
bool uu[125255],cc[505];
int h[505],bs[505],par[505],tp,a,b,cur,tpans,nw;
vector<int>vv[505];
int F(int N)
{
    if(bs[N]==N)return N;
    else return bs[N]=F(bs[N]);
}
void un(int X,int Y)
{
    bs[F(X)]=F(Y);
    return;
}
void dfs(int N,int pr,int H)
{
    par[N]=pr;
    h[N]=H;
    for(int i=0;i<vv[N].size();i++)
    {
        if(vv[N][i]==pr)continue;
        dfs(vv[N][i],N,H+1);
    }
    return;
}
vector<int> find_roads(int n,vector<int>u,vector<int>v)
{
    vector<int>ryl;
	vector<int>ans;
    for(int i=0;i<n;i++)bs[i]=i;
    for(int i=0;i<u.size();i++)
    {
        uu[i]=false;
       // printf("%d %d\n",F(u[i]),F(v[i]));
        if(F(u[i])==F(v[i]))continue;
        un(u[i],v[i]);
       // printf("[%d]",i);
        ans.pb(i);
        ryl.pb(0);
        uu[i]=true;
    }
    tp=count_common_roads(ans);
    for(int i=0;i<u.size();i++)
    {
        if(uu[i])continue;
        a=u[i],b=v[i];
        for(int i=0;i<n;i++)vv[i].clear();
        for(int i=0;i<ans.size();i++)vv[u[ans[i]]].pb(v[ans[i]]),vv[v[ans[i]]].pb(u[ans[i]]);
        dfs(1,-1,1);
		//for(int i=0;i<n;i++)printf("%d %d %d\n",par[i],h[i],i);
        if(h[a]<h[b])swap(a,b);
        while(h[a]>h[b])
        {
            for(int i=0;i<ans.size();i++)
            {
                if((a==u[ans[i]]&&par[a]==v[ans[i]])||(par[a]==u[ans[i]]&&a==v[ans[i]]))cur=i;
            }
            a=par[a];
            tpans=ans[cur];
            ans[cur]=i;
            if(!cc[cur])nw=count_common_roads(ans);
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
        }
        if(nw>tp)
        {
            tp=nw;
            continue;
        }
        while(a!=b)
        {
            for(int i=0;i<ans.size();i++)
            {
                if((a==u[ans[i]]&&par[a]==v[ans[i]])||(par[a]==u[ans[i]]&&a==v[ans[i]]))cur=i;
            }
            a=par[a];
            tpans=ans[cur];
            ans[cur]=i;
            if(!cc[cur])nw=count_common_roads(ans);
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
            for(int i=0;i<ans.size();i++)
            {
                if((b==u[ans[i]]&&par[b]==v[ans[i]])||(par[b]==u[ans[i]]&&b==v[ans[i]]))cur=i;
            }
            b=par[b];
            tpans=ans[cur];
            ans[cur]=i;
            if(!cc[cur])nw=count_common_roads(ans);
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
        }
        if(nw>tp)
        {
            tp=nw;
            continue;
        }
    }
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<vv[N].size();i++)
      |                 ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<ans.size();i++)vv[u[ans[i]]].pb(v[ans[i]]),vv[v[ans[i]]].pb(u[ans[i]]);
      |                     ~^~~~~~~~~~~
simurgh.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~

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