oj.uz

Submission #821217

# Submission time Handle Problem Language Result Execution time Memory
821217 2023-08-11T08:11:58 Z vjudge1 Simurgh (IOI17_simurgh) C++14
13 / 100
 1216 ms 308 KB 
#include<bits/stdc++.h>
#include "simurgh.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 500 ;
//void Answer(vector<int>& res)
//{
//    cout << "! " ;
//    for(int i : res)
//        cout << i << ' ' ;
//    exit(0) ;
//}
//int count_common_roads(vector<int> r)
//{
//    int num ;
//    cout << "? " ;
//    for(int i : r)
//        cout << i << ' ' ;
//    cout << '\n' ;
//    cin >> num ;
//    return num ;
//}
int cnt ;
bool us[N + 1] ;
vector<int> v[N + 1] ;
void dfs(int city)
{
    cnt++ ;
    us[city] = 1 ;
    for(int i : v[city])
    {
        if(us[i])
            continue ;
        dfs(i) ;
    }
}
void ultra_clear()
{
    cnt &= 0 ;
    for(int i = 0 ; i < N ; i++)
        us[i] &= 0, v[i].clear() ;
}
vector<int> find_roads(int n, vector<int> fr, vector<int> to)
{
    vector<int> ans ;
    int m = fr.size() ;
    if(n <= 7)
    {
        for(int i = 0 ; i < (1 << m) ; i++)
        {
            ultra_clear() ;
            vector<int> qr ;
            for(int j = 0 ; j < m ; j++)
            {
                if(!((1 << j) & i))
                    continue ;
                qr.push_back(j) ;
                v[fr[j]].push_back(to[j]) ;
                v[to[j]].push_back(fr[j]) ;
            }
            dfs(0) ;
            if(qr.size() == n - 1 && cnt == n && count_common_roads(qr) == n - 1)
            {
                ans = qr ;
                break ;
            }
        }
    }
    return ans ;
}
//signed main()
//{
//    int n, m ;
//    cin >> n >> m ;
//    vector<int> fr(m), to(m) ;
//    for(int i = 0 ; i < m ; i++)
//        cin >> fr[i] >> to[i] ;
//    vector<int> res = find_roads(n, fr, to) ;
//    Answer(res) ;
//    return 0 ;
//}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:64:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |             if(qr.size() == n - 1 && cnt == n && count_common_roads(qr) == n - 1)
      |                ~~~~~~~~~~^~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 212 KB correct
2 Correct 927 ms 288 KB correct
3 Correct 1216 ms 288 KB correct
4 Correct 5 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 22 ms 304 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 6 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 11 ms 308 KB correct
13 Correct 296 ms 284 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 212 KB correct
2 Correct 927 ms 288 KB correct
3 Correct 1216 ms 288 KB correct
4 Correct 5 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 22 ms 304 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 6 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 11 ms 308 KB correct
13 Correct 296 ms 284 KB correct
14 Incorrect 0 ms 212 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 212 KB correct
2 Correct 927 ms 288 KB correct
3 Correct 1216 ms 288 KB correct
4 Correct 5 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 22 ms 304 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 6 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 11 ms 308 KB correct
13 Correct 296 ms 284 KB correct
14 Incorrect 0 ms 212 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 212 KB correct
2 Correct 927 ms 288 KB correct
3 Correct 1216 ms 288 KB correct
4 Correct 5 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 22 ms 304 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 6 ms 308 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 11 ms 308 KB correct
13 Correct 296 ms 284 KB correct
14 Incorrect 0 ms 212 KB WA in grader: NO
15 Halted 0 ms 0 KB -