oj.uz

답안 #1046295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046295 2024-08-06T12:36:24 Z vanea 슈퍼트리 잇기 (IOI20_supertrees) C++14
11 / 100
 111 ms 22252 KB 
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
using ld = long double;

const int mxN = 1e3+10;

int p[mxN];

vector<int> adj[mxN];
int type[mxN];

int get(int x) {
    return p[x] < 0 ? x : p[x] = get(p[x]);
}

void uni(int a, int b) {
    a = get(a); b = get(b);
    if(a == b) return ;
    if(p[a] > p[b]) swap(a, b);
    p[a] += p[b];
    p[b] = a;
}

int construct(vector<vector<int>> P) {
    int n = P.size();
    for(int i = 0; i < n; i++) p[i] = -1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            if(P[i][j] == 1 && (get(i) != get(j))) {
                uni(i, j);
                adj[i].push_back(j);
                adj[j].push_back(i);
                type[i] = 1; type[j] = 1;
            }
        }
    }
    bool pos = true;
    for(int i = 0; i < n; i++) {
        vector<int> v;
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            if(P[i][j] == 2 && (get(j) != get(i))) v.push_back(j);
        }
        if(v.empty()) continue;
        if(v.size() == 1) {
            pos = false;
            break;
        }
        int x = get(i);
        for(int i = 0; i + 1 < v.size(); i++) {
            adj[v[i]].push_back(v[i+1]);
            adj[v[i+1]].push_back(v[i]);
            uni(v[i], v[i+1]);
            type[v[i]] = 2;
            type[v[i+1]] = 2;
        }
        adj[x].push_back(v[0]);
        adj[v[0]].push_back(x);
        adj[v[v.size()-1]].push_back(x);
        adj[x].push_back(v[v.size()-1]);
        uni(x, v[0]);
    }
    //if(!pos) return 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            if(P[i][j]) {
                if(get(i) != get(j)) pos = false;
                else {
                    if(P[i][j] == 1) {
                        if(type[i] != 1 || type[j] != 1) pos = false;
                    }
                    else {
                        if(type[i] == 1 && type[j] == 1) pos = false;
                    }
                }
            }
            else {
                if(get(i) == get(j)) pos = false;
            }
        }
    }
    //if(!pos) return 0;
    vector<vector<int>> ans(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        for(auto it : adj[i]) {
            ans[i][it] = ans[it][i] = 1;
        }
    }
    build(ans);
    return 1;
}

/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<vector<int>> a = {{1, 1, 1, 1, 1, 1, 2, 2, 2},
    {1, 1, 1, 1, 1, 1, 2, 2, 2},
    {1, 1, 1, 1, 1, 1, 2, 2, 2},
    {1, 1, 1, 1, 1, 1, 2, 2, 2},
    {1, 1, 1, 1, 1, 1, 2, 2, 2},
    {1, 1, 1, 1, 1, 1, 2, 2, 2},
    {2, 2, 2, 2, 2, 2, 1, 2, 2},
    {2, 2, 2, 2, 2, 2, 2, 1, 2},
    {2, 2, 2, 2, 2, 2, 2, 2, 1}};
    cout << construct(a);
}*/

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i = 0; i + 1 < v.size(); i++) {
      |                        ~~~~~~^~~~~~~~~~
supertrees.cpp:40:10: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   40 |     bool pos = true;
      |          ^~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 103 ms 22100 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 103 ms 22100 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 97 ms 22076 KB Output is correct
14 Incorrect 0 ms 600 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

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

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 24 ms 5896 KB Output is correct
5 Correct 99 ms 22252 KB Output is correct
6 Correct 98 ms 22096 KB Output is correct
7 Correct 103 ms 22072 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 24 ms 5772 KB Output is correct
10 Correct 111 ms 22100 KB Output is correct
11 Correct 105 ms 22096 KB Output is correct
12 Correct 105 ms 22048 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 27 ms 5840 KB Too many ways to get from 0 to 250, should be 2 found no less than 3
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 103 ms 22100 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 97 ms 22076 KB Output is correct
14 Incorrect 0 ms 600 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 103 ms 22100 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 97 ms 22076 KB Output is correct
14 Incorrect 0 ms 600 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -