oj.uz

답안 #1075619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1075619 2024-08-26T08:00:51 Z edogawa_something Simurgh (IOI17_simurgh) C++17
13 / 100
 14 ms 604 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
struct dsu {
  ll pa[50];
  void init(ll x) {
    for(int i=0;i<=x;i++)
      pa[i]=i;
  }
  ll get(ll x) {
    if(x==pa[x])
      return x;
    return pa[x]=get(pa[x]);
  }
  bool unite(ll x,ll y) {
    x=get(x),y=get(y);
    if(x==y)
    return 0;
    pa[x]=y;
    return 1;
  }
}d;
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> vv) {
  for(int i=0;i<(1<<(u.size()));i++) {
    if(__builtin_popcount(i)==n-1) {
      vector<int>v;
      d.init(n);
      bool chk=1;
      for(int bit=0;bit<u.size();bit++) {
        if(((1<<bit)&i)) {
          chk&=d.unite(u[bit],vv[bit]);
          v.pb(bit);
        }
      }
      if(chk) {
        ll x=count_common_roads(v);
        if(x==n-1) {
          return v;
        }
      }
    }
  }
  return {};
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |       for(int bit=0;bit<u.size();bit++) {
      |                     ~~~^~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 604 KB correct
2 Correct 13 ms 348 KB correct
3 Correct 14 ms 348 KB correct
4 Correct 1 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 436 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 352 KB correct
13 Correct 7 ms 348 KB correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 604 KB correct
2 Correct 13 ms 348 KB correct
3 Correct 14 ms 348 KB correct
4 Correct 1 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 436 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 352 KB correct
13 Correct 7 ms 348 KB correct
14 Incorrect 0 ms 348 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 604 KB correct
2 Correct 13 ms 348 KB correct
3 Correct 14 ms 348 KB correct
4 Correct 1 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 436 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 352 KB correct
13 Correct 7 ms 348 KB correct
14 Incorrect 0 ms 348 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB correct
2 Incorrect 1 ms 348 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 604 KB correct
2 Correct 13 ms 348 KB correct
3 Correct 14 ms 348 KB correct
4 Correct 1 ms 344 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 436 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 1 ms 352 KB correct
13 Correct 7 ms 348 KB correct
14 Incorrect 0 ms 348 KB WA in grader: NO
15 Halted 0 ms 0 KB -