oj.uz

Submission #73948

# Submission time Handle Problem Language Result Execution time Memory
73948 2018-08-29T10:15:45 Z Batmend4 Simurgh (IOI17_simurgh) C++
30 / 100
 156 ms 4072 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;
    map<int, bool> usedh;
    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++ ){
            if( ed[i][j].first > i && usedh[ed[i][j].second] ) continue;
            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;
                if( usedh[impo[j][ii].second] == 1 ) continue;
                usedh[impo[j][ii].second] = 1;
                motherfickinggoldenroads.push_back(impo[j][ii].second);
            }
        }
    }
    return motherfickinggoldenroads;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:11:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i = 0 ; i < u.size() ; i++ ){
                      ~~^~~~~~~~~~
simurgh.cpp:31:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for( int i = 0 ; i < ed[x].size() ; i++ ){
                                  ~~^~~~~~~~~~~~~~
simurgh.cpp:43:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0 ; j < ed[i].size() ; j++ ){
                          ~~^~~~~~~~~~~~~~
simurgh.cpp:49:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j = 0 ; j < ed[i].size() ; j++ ){
                          ~~^~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB correct
2 Correct 3 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 3 ms 492 KB correct
7 Correct 2 ms 492 KB correct
8 Correct 2 ms 492 KB correct
9 Correct 2 ms 568 KB correct
10 Correct 2 ms 568 KB correct
11 Correct 3 ms 568 KB correct
12 Correct 3 ms 568 KB correct
13 Correct 3 ms 568 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB correct
2 Correct 3 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 3 ms 492 KB correct
7 Correct 2 ms 492 KB correct
8 Correct 2 ms 492 KB correct
9 Correct 2 ms 568 KB correct
10 Correct 2 ms 568 KB correct
11 Correct 3 ms 568 KB correct
12 Correct 3 ms 568 KB correct
13 Correct 3 ms 568 KB correct
14 Correct 6 ms 616 KB correct
15 Correct 5 ms 616 KB correct
16 Correct 6 ms 616 KB correct
17 Correct 7 ms 616 KB correct
18 Correct 4 ms 616 KB correct
19 Correct 5 ms 616 KB correct
20 Correct 7 ms 744 KB correct
21 Correct 5 ms 744 KB correct
22 Correct 4 ms 744 KB correct
23 Correct 7 ms 744 KB correct
24 Correct 5 ms 744 KB correct
25 Correct 3 ms 744 KB correct
26 Correct 4 ms 744 KB correct
27 Correct 4 ms 744 KB correct
28 Correct 3 ms 744 KB correct
29 Correct 2 ms 744 KB correct
30 Correct 3 ms 744 KB correct
31 Correct 5 ms 744 KB correct
32 Correct 3 ms 744 KB correct
33 Correct 4 ms 744 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB correct
2 Correct 3 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 3 ms 492 KB correct
7 Correct 2 ms 492 KB correct
8 Correct 2 ms 492 KB correct
9 Correct 2 ms 568 KB correct
10 Correct 2 ms 568 KB correct
11 Correct 3 ms 568 KB correct
12 Correct 3 ms 568 KB correct
13 Correct 3 ms 568 KB correct
14 Correct 6 ms 616 KB correct
15 Correct 5 ms 616 KB correct
16 Correct 6 ms 616 KB correct
17 Correct 7 ms 616 KB correct
18 Correct 4 ms 616 KB correct
19 Correct 5 ms 616 KB correct
20 Correct 7 ms 744 KB correct
21 Correct 5 ms 744 KB correct
22 Correct 4 ms 744 KB correct
23 Correct 7 ms 744 KB correct
24 Correct 5 ms 744 KB correct
25 Correct 3 ms 744 KB correct
26 Correct 4 ms 744 KB correct
27 Correct 4 ms 744 KB correct
28 Correct 3 ms 744 KB correct
29 Correct 2 ms 744 KB correct
30 Correct 3 ms 744 KB correct
31 Correct 5 ms 744 KB correct
32 Correct 3 ms 744 KB correct
33 Correct 4 ms 744 KB correct
34 Incorrect 140 ms 2604 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 2604 KB correct
2 Correct 3 ms 2604 KB correct
3 Incorrect 156 ms 4072 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 248 KB correct
2 Correct 3 ms 484 KB correct
3 Correct 2 ms 484 KB correct
4 Correct 2 ms 484 KB correct
5 Correct 3 ms 492 KB correct
6 Correct 3 ms 492 KB correct
7 Correct 2 ms 492 KB correct
8 Correct 2 ms 492 KB correct
9 Correct 2 ms 568 KB correct
10 Correct 2 ms 568 KB correct
11 Correct 3 ms 568 KB correct
12 Correct 3 ms 568 KB correct
13 Correct 3 ms 568 KB correct
14 Correct 6 ms 616 KB correct
15 Correct 5 ms 616 KB correct
16 Correct 6 ms 616 KB correct
17 Correct 7 ms 616 KB correct
18 Correct 4 ms 616 KB correct
19 Correct 5 ms 616 KB correct
20 Correct 7 ms 744 KB correct
21 Correct 5 ms 744 KB correct
22 Correct 4 ms 744 KB correct
23 Correct 7 ms 744 KB correct
24 Correct 5 ms 744 KB correct
25 Correct 3 ms 744 KB correct
26 Correct 4 ms 744 KB correct
27 Correct 4 ms 744 KB correct
28 Correct 3 ms 744 KB correct
29 Correct 2 ms 744 KB correct
30 Correct 3 ms 744 KB correct
31 Correct 5 ms 744 KB correct
32 Correct 3 ms 744 KB correct
33 Correct 4 ms 744 KB correct
34 Incorrect 140 ms 2604 KB WA in grader: NO
35 Halted 0 ms 0 KB -