Submission #1075675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075675		amin	Simurgh (IOI17_simurgh)	C++14	0 / 100	0 ms	348 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj;
vector<int>q;
int pa[1000000];
int mark[1000000];
int par(int x)
{

    if(pa[x]==x)
        return x;
    pa[x]=par(pa[x]);
    return pa[x];
}
void mer(int x,int y)
{
    if(x==y)
        return ;
    pa[y]=x;


}
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
    int m=v.size();
    vector<int>ans;

    while(ans.size()<n-1)
    {
      //  cout<<ans.size()<<endl;
        int no=n;
        q.clear();
        for(int i=0; i<n; i++)
            pa[i]=i;
        for(int i=0; i<ans.size(); i++)
        {

                q.push_back(ans[i]);
                mer(u[ans[i]],v[ans[i]]);


        }
        no=n-ans.size();

            for(int i=0; i<m; i++)
        {
            int x=u[i];
            int y=v[i];
            x=par(x);
            y=par(y);
            if(x!=y&&no>2)
            {
                q.push_back(i);
                no--;
                mer(x,y);

            }
        }

            int co=-1;
            stack<int>s;
            for(int i=0; i<m; i++)
        {
            int x=u[i];
            int y=v[i];
            x=par(x);
            y=par(y);
            if(mark[i]==0&&x!=y)
            {
                mark[i]=1;
                q.push_back(i);
              //  s.push(i);
               int j=count_common_roads(q);

               if(j!=co&&co!=-1)
               {
                   if(j>co)
                   {
                       while(!s.empty())
                       {
                           s.pop();
                       }
                       ans.push_back(i);
                   }else
                   {
                         while(!s.empty())
                       {
                           ans.push_back(s.top());

                           s.pop();
                       }
                   }
                   break;
               }
               s.push(i);
                co=j;
               q.pop_back();

            }

        }
         while(!s.empty())
                       {
                           ans.push_back(s.top());

                           s.pop();
                       }
    }

    return ans;


}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     while(ans.size()<n-1)
      |           ~~~~~~~~~~^~~~
simurgh.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i=0; i<ans.size(); i++)
      |                      ~^~~~~~~~~~~

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