Submission #429611

#	Time	Username	Problem	Language	Result	Execution time	Memory
429611		inwbear	Simurgh (IOI17_simurgh)	C++14	30 / 100	206 ms	1852 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
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];
vector<pair<int,int> >pss;
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);
                pss.pb({cur,nw});
            }
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
        }
        if(nw>tp)
        {
            tp=nw;
            for(int i=0;i<pss.size();i++)
            {
                if(pss[i].S==nw)cc[pss[i].F]=true;
            }
            pss.clear();
            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);
                pss.pb({cur,nw});
            }
            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);
                pss.pb({cur,nw});
            }
            if(nw>tp)
			{
				cc[cur]=true;
				break;
			}
            ans[cur]=tpans;
        }
        if(nw>tp)
        {
            tp=nw;
            for(int i=0;i<pss.size();i++)
            {
                if(pss[i].S==nw)cc[pss[i].F]=true;
            }
            pss.clear();
            continue;
        }
    }
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     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:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         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:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:82:26: 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<pss.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             for(int i=0;i<ans.size();i++)
      |                         ~^~~~~~~~~~~
simurgh.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             for(int i=0;i<pss.size();i++)
      |                         ~^~~~~~~~~~~

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