oj.uz

답안 #370643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370643 2021-02-24T11:05:50 Z anakib1 슈퍼트리 잇기 (IOI20_supertrees) C++17
21 / 100
 300 ms 22380 KB 
//나는 가상 소녀들에게 큰 호감이 있습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define sz(a) (int)(a.size())
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define problem "a"

template<typename A, typename B, typename C>
struct triple {
    A X;
    B Y;
    C Z;
    triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
    return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
    if (a.X != b.X)
        return a.X < b.X;
    if (a.Y != b.Y)
        return a.Y < b.Y;
    return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
    ofs << "( " << p.F << " , " << p.S << " )";
    return ofs;
}
template<typename T>
void print(T a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
template<typename T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}
template<typename T, typename D>
D min(T a) {
    return *min_element(all(a));
}
template<typename T, typename D>
D max(T a) {
    return *max_element(all(a));
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#include "supertrees.h"

int construct(std::vector<std::vector<int>> p) {
    int n = sz(p);
    vi pp(n); iota(all(pp), 0);
    function<int(int)> get = [&](int x) {
        if (x == pp[x])return x; return pp[x] = get(pp[x]);
    };
    auto mrg = [&](int x, int y) {
        x = get(x); y = get(y);
        if (x == y)return 0;
        if (rand() & 1)swap(x, y); pp[x] = y; return 1;
    };
    auto same = [&](int x, int y) {return get(x) == get(y); };
    rngi(i, n) for (int j = i + 1; j < n; j++) if (p[i][j]) mrg(i, j);
    rngi(j, n) rngi(i, j) if (!p[i][j] && same(i, j)) return 0;
    vector<vi> cmp(n); rngi(i, n) cmp[get(i)].push_back(i);
    vector < vi > b(n, vi(n));
    rngi(i, n) 
        rngi(j, sz(cmp[i]) - 1) b[cmp[i][0]][cmp[i][j + 1]] = b[cmp[i][j + 1]][cmp[i][0]] = 1;
    build(b);
    return 1;
}

Compilation message

supertrees.cpp: In lambda function:
supertrees.cpp:118:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  118 |         if (x == pp[x])return x; return pp[x] = get(pp[x]);
      |         ^~
supertrees.cpp:118:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  118 |         if (x == pp[x])return x; return pp[x] = get(pp[x]);
      |                                  ^~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:123:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  123 |         if (rand() & 1)swap(x, y); pp[x] = y; return 1;
      |         ^~
supertrees.cpp:123:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  123 |         if (rand() & 1)swap(x, y); pp[x] = y; return 1;
      |                                    ^~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 1260 KB Output is correct
7 Correct 252 ms 22124 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 1260 KB Output is correct
7 Correct 252 ms 22124 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1260 KB Output is correct
13 Correct 254 ms 22160 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 620 KB Output is correct
17 Correct 116 ms 8312 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 76 ms 5868 KB Output is correct
21 Correct 262 ms 22124 KB Output is correct
22 Correct 261 ms 22124 KB Output is correct
23 Correct 300 ms 22380 KB Output is correct
24 Correct 248 ms 22124 KB Output is correct
25 Correct 106 ms 8172 KB Output is correct
26 Correct 122 ms 8172 KB Output is correct
27 Correct 278 ms 22124 KB Output is correct
28 Correct 245 ms 22124 KB Output is correct

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Too few ways to get from 0 to 1, should be 2 found 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 1260 KB Output is correct
7 Correct 252 ms 22124 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1260 KB Output is correct
13 Correct 254 ms 22160 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 620 KB Output is correct
17 Correct 116 ms 8312 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 76 ms 5868 KB Output is correct
21 Correct 262 ms 22124 KB Output is correct
22 Correct 261 ms 22124 KB Output is correct
23 Correct 300 ms 22380 KB Output is correct
24 Correct 248 ms 22124 KB Output is correct
25 Correct 106 ms 8172 KB Output is correct
26 Correct 122 ms 8172 KB Output is correct
27 Correct 278 ms 22124 KB Output is correct
28 Correct 245 ms 22124 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Incorrect 1 ms 364 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 1260 KB Output is correct
7 Correct 252 ms 22124 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 11 ms 1260 KB Output is correct
13 Correct 254 ms 22160 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 620 KB Output is correct
17 Correct 116 ms 8312 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 76 ms 5868 KB Output is correct
21 Correct 262 ms 22124 KB Output is correct
22 Correct 261 ms 22124 KB Output is correct
23 Correct 300 ms 22380 KB Output is correct
24 Correct 248 ms 22124 KB Output is correct
25 Correct 106 ms 8172 KB Output is correct
26 Correct 122 ms 8172 KB Output is correct
27 Correct 278 ms 22124 KB Output is correct
28 Correct 245 ms 22124 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 0 ms 364 KB Output is correct
32 Incorrect 1 ms 364 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -