Submission #73927

#	Time	Username	Problem	Language	Result	Execution time	Memory
73927		Batmend4	Simurgh (IOI17_simurgh)	C++98	30 / 100	181 ms	3716 KiB

simurgh

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



vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    vector<int> motherfickinggoldenroads;
    vector< pair<int, int> > ed[n];
    for( int i = 0 ; i < u.size() ; i++ ){
        ed[u[i]].push_back(make_pair( v[i], i) );
        ed[v[i]].push_back(make_pair( u[i], i) );
    }
    
    for( int i = 0 ; i < n ; i++ ){
        vector<int> ct;
        int pos = 0;
        int used[n];
        memset(used, -1, sizeof used);
        used[i] = 1000000007;
        for( int j = 0 ; j < n ; j++ ){
            if( used[j] != -1 ) continue;
            queue< int >q;
            q.push(j);
            used[j] = pos;
            
            while( !q.empty()){
                int x = q.front();
                q.pop();
                for( int i = 0 ; i < ed[x].size() ; i++ ){
                    if( used[ed[x][i].first] != -1 ) continue;
                    ct.push_back( ed[x][i].second );
                    used[ed[x][i].first] = pos;
                    q.push( ed[x][i].first);
                }
            }
        
            pos++;
        }
        vector<int> edge[pos + 5];
        vector<pair<int, int> > impo[pos + 5];
        for( int j = 0 ; j < ed[i].size() ; j++ ){
            edge[used[ed[i][j].first]].push_back(ed[i][j].second);
        }
        for( int j = 0 ; j < pos ; j++ ){
            ct.push_back(edge[j][0]);
        }
        for( int j = 0 ; j < ed[i].size() ; j++ ){
            ct[n - 2 - (pos - 1) + used[ed[i][j].first]] = ed[i][j].second;
            impo[used[ed[i][j].first]].push_back(make_pair(count_common_roads(ct), ed[i][j].second));
        }
        for( int j = 0 ; j < pos ; j++ ){
            sort( impo[j].begin(), impo[j].end() );
            bool lol = 1;
            int si = impo[j].size();
            int x = impo[j][si - 1].first;
            for( int ii = si - 1 ; ii >= 0 ; ii-- ){
                if( impo[j][ii].first != x )lol = 0;
                if (lol == 0) continue;
                motherfickinggoldenroads.push_back(impo[j][ii].second);
            }
        }
    }
    sort( motherfickinggoldenroads.begin(), motherfickinggoldenroads.end());
    vector<int> realmotherfickinggoldenroads;
    for( int i = 0 ; i < motherfickinggoldenroads.size() / 2; i++ ){
        realmotherfickinggoldenroads.push_back(motherfickinggoldenroads[i * 2]);
    }
    return realmotherfickinggoldenroads;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:10:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < u.size() ; i++ ){
                      ~~^~~~~~~~~~
simurgh.cpp:30:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for( int i = 0 ; i < ed[x].size() ; i++ ){
                                  ~~^~~~~~~~~~~~~~
simurgh.cpp:42:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0 ; j < ed[i].size() ; j++ ){
                          ~~^~~~~~~~~~~~~~
simurgh.cpp:48:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0 ; j < ed[i].size() ; j++ ){
                          ~~^~~~~~~~~~~~~~
simurgh.cpp:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < motherfickinggoldenroads.size() / 2; i++ ){
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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