oj.uz

답안 #1047558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047558 2024-08-07T14:02:33 Z idas 슈퍼트리 잇기 (IOI20_supertrees) C++17
0 / 100
 0 ms 348 KB 
#include "supertrees.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back

using namespace std;
typedef long long ll;
typedef vector<int> vi;

const int MxN=1e3+10;
int n, par[MxN], cyc[MxN];
bool v[MxN];

int fnd(int u) {
    return par[u]=par[u]==u?u:fnd(par[u]);
}

void mrg(int a, int b) {
    a=fnd(a); b=fnd(b);
    if(a==b) return;
    par[a]=b;
}

int construct(std::vector<std::vector<int>> p) {
    n=sz(p);

    FOR(i, 0, n) par[i]=i;

    vector b(n, vector(n, 0));
    FOR(i, 0, n) {
        FOR(j, 0, n) {
            if(p[i][j]==1) {
                b[i][j]=b[j][i]=1;
                mrg(i, j);
            }
        }
    }

    vector used(n, false);
    FOR(i, 0, n) {
        int u=fnd(i);
        if(used[u]) continue;

        used[u]=true;
        cyc[u]=i;

        int cn=1, lst=u, frst=u;
        FOR(j, 0, n) {
            int w=fnd(j);
            if(used[w]) continue;

            if(p[u][w]==2) {
                used[w]=true;
                cyc[w]=i;
                cn++;

                b[lst][w]=b[w][lst]=1;
                lst=w;
            }
        }
        b[lst][frst]=b[frst][lst]=1;

        if(cn<=2) {
            return 0;
        }
    }

    bool ok=true;
    FOR(i, 0, n) {
        FOR(j, 0, n) {
            int u=fnd(i), w=fnd(j);
            if(u==w) ok&=p[u][w]==1;
            else if(cyc[u]==cyc[w]) ok&=p[u][w]==2;
            else ok&=p[u][w]==0;
        }
    }

    if(!ok) return 0;

    build(b);

    return 1;
}
/*
5
1 1 2 2 2
1 1 2 2 2
2 2 1 2 2
2 2 2 1 1
2 2 2 1 1
*/

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -