Submission #366052

#	Time	Username	Problem	Language	Result	Execution time	Memory
366052		denkendoemeer	Simurgh (IOI17_simurgh)	C++14	51 / 100	199 ms	3940 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>ans,poz,poz2,g,g2;
int t[505],n,m;
void init()
{
    int i;
    for(i=0;i<n;i++)
        t[i]=i;
}
int findt(int nod)
{
    if (nod==t[nod])
        return nod;
    return t[nod]=findt(t[nod]);
}
void onion(int x,int y)
{
    x=findt(x);
    y=findt(y);
    t[x]=y;
}
void calc()
{
    init();
    int cnt=n;
    vector<int>aux;
    vector<pair<int,int>>auxi;
    for(auto it:ans){
        onion(g[it],g2[it]);
        aux.push_back(it);
        cnt--;
    }
    for(auto it:poz){
        if (cnt==2){
            if (findt(g[it])!=findt(g2[it])){
                aux.push_back(it);
                int nr=count_common_roads(aux);
                auxi.push_back({nr,it});
                aux.pop_back();
            }
            else
                poz2.push_back(it);
        }
        else{
            if (findt(g[it])!=findt(g2[it])){
                aux.push_back(it);
                onion(g[it],g2[it]);
                cnt--;
            }
            poz2.push_back(it);
        }
    }
    pair<int,int>maxi=*max_element(auxi.begin(),auxi.end());
    for(auto it:auxi)
        if (it.first==maxi.first)
            ans.push_back(it.second);
    swap(poz,poz2);
    poz2.clear();
}
vector<int> find_roads(int n2,vector<int>x,vector<int>y)
{
    m=x.size();
    n=n2;
    g=x;
    g2=y;
    int i;
    for(i=0;i<m;i++)
        poz.push_back(i);
    while(ans.size()<n-1)
        calc();
    return ans;
}

Compilation message (stderr)

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

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