Submission #821217

#	Time	Username	Problem	Language	Result	Execution time	Memory
821217		vjudge1	Simurgh (IOI17_simurgh)	C++14	13 / 100	1216 ms	308 KiB

simurgh

#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 (stderr)

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 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30