oj.uz

Submission #73927

# Submission time Handle Problem Language Result Execution time Memory
73927 2018-08-29T09:32:54 Z Batmend4 Simurgh (IOI17_simurgh) C++
30 / 100
 181 ms 3716 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 436 KB correct
4 Correct 3 ms 452 KB correct
5 Correct 4 ms 508 KB correct
6 Correct 3 ms 516 KB correct
7 Correct 4 ms 652 KB correct
8 Correct 2 ms 652 KB correct
9 Correct 3 ms 652 KB correct
10 Correct 3 ms 652 KB correct
11 Correct 2 ms 652 KB correct
12 Correct 2 ms 652 KB correct
13 Correct 3 ms 652 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 436 KB correct
4 Correct 3 ms 452 KB correct
5 Correct 4 ms 508 KB correct
6 Correct 3 ms 516 KB correct
7 Correct 4 ms 652 KB correct
8 Correct 2 ms 652 KB correct
9 Correct 3 ms 652 KB correct
10 Correct 3 ms 652 KB correct
11 Correct 2 ms 652 KB correct
12 Correct 2 ms 652 KB correct
13 Correct 3 ms 652 KB correct
14 Correct 6 ms 652 KB correct
15 Correct 5 ms 652 KB correct
16 Correct 5 ms 652 KB correct
17 Correct 5 ms 652 KB correct
18 Correct 5 ms 652 KB correct
19 Correct 6 ms 652 KB correct
20 Correct 6 ms 652 KB correct
21 Correct 4 ms 652 KB correct
22 Correct 4 ms 652 KB correct
23 Correct 4 ms 652 KB correct
24 Correct 4 ms 652 KB correct
25 Correct 3 ms 652 KB correct
26 Correct 4 ms 652 KB correct
27 Correct 4 ms 652 KB correct
28 Correct 3 ms 652 KB correct
29 Correct 4 ms 652 KB correct
30 Correct 5 ms 652 KB correct
31 Correct 5 ms 652 KB correct
32 Correct 4 ms 652 KB correct
33 Correct 5 ms 652 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 436 KB correct
4 Correct 3 ms 452 KB correct
5 Correct 4 ms 508 KB correct
6 Correct 3 ms 516 KB correct
7 Correct 4 ms 652 KB correct
8 Correct 2 ms 652 KB correct
9 Correct 3 ms 652 KB correct
10 Correct 3 ms 652 KB correct
11 Correct 2 ms 652 KB correct
12 Correct 2 ms 652 KB correct
13 Correct 3 ms 652 KB correct
14 Correct 6 ms 652 KB correct
15 Correct 5 ms 652 KB correct
16 Correct 5 ms 652 KB correct
17 Correct 5 ms 652 KB correct
18 Correct 5 ms 652 KB correct
19 Correct 6 ms 652 KB correct
20 Correct 6 ms 652 KB correct
21 Correct 4 ms 652 KB correct
22 Correct 4 ms 652 KB correct
23 Correct 4 ms 652 KB correct
24 Correct 4 ms 652 KB correct
25 Correct 3 ms 652 KB correct
26 Correct 4 ms 652 KB correct
27 Correct 4 ms 652 KB correct
28 Correct 3 ms 652 KB correct
29 Correct 4 ms 652 KB correct
30 Correct 5 ms 652 KB correct
31 Correct 5 ms 652 KB correct
32 Correct 4 ms 652 KB correct
33 Correct 5 ms 652 KB correct
34 Incorrect 181 ms 1772 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB correct
2 Correct 4 ms 1772 KB correct
3 Incorrect 132 ms 3716 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 3 ms 436 KB correct
4 Correct 3 ms 452 KB correct
5 Correct 4 ms 508 KB correct
6 Correct 3 ms 516 KB correct
7 Correct 4 ms 652 KB correct
8 Correct 2 ms 652 KB correct
9 Correct 3 ms 652 KB correct
10 Correct 3 ms 652 KB correct
11 Correct 2 ms 652 KB correct
12 Correct 2 ms 652 KB correct
13 Correct 3 ms 652 KB correct
14 Correct 6 ms 652 KB correct
15 Correct 5 ms 652 KB correct
16 Correct 5 ms 652 KB correct
17 Correct 5 ms 652 KB correct
18 Correct 5 ms 652 KB correct
19 Correct 6 ms 652 KB correct
20 Correct 6 ms 652 KB correct
21 Correct 4 ms 652 KB correct
22 Correct 4 ms 652 KB correct
23 Correct 4 ms 652 KB correct
24 Correct 4 ms 652 KB correct
25 Correct 3 ms 652 KB correct
26 Correct 4 ms 652 KB correct
27 Correct 4 ms 652 KB correct
28 Correct 3 ms 652 KB correct
29 Correct 4 ms 652 KB correct
30 Correct 5 ms 652 KB correct
31 Correct 5 ms 652 KB correct
32 Correct 4 ms 652 KB correct
33 Correct 5 ms 652 KB correct
34 Incorrect 181 ms 1772 KB WA in grader: NO
35 Halted 0 ms 0 KB -