oj.uz

Submission #301156

# Submission time Handle Problem Language Result Execution time Memory
301156 2020-09-17T17:00:45 Z andrew Connecting Supertrees (IOI20_supertrees) C++17
0 / 100
 1 ms 256 KB 
#include <bits/stdc++.h>
#include "supertrees.h"


#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define p_b push_back

using namespace std;
typedef long long ll;
const ll N = 2e3;

int p1[N], p2[N];

int get(int x){
    if(p1[x] != x)p1[x] = get(p1[x]);
    return p1[x];
}

int get1(int x){
    if(p2[x] != x)p2[x] = get1(p2[x]);
    return p2[x];
}

int construct(vector <vector <int> > p){
    int n = sz(p);
    vector <vector <int> > answer(n, vector <int> (n, 0));
    vector <vector <int> > mb(n, vector <int> (n, 0));
    iota(p1, p1 + n, 0);
    iota(p2, p2 + n, 0);
    int msk = 1;
    for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++){
        if(p[i][j] == 1 && get(i) != get(j))p1[get(i)] = get(j);
        msk |= 1 << p[i][j];
    }
    for(int i = 0; i < n; i++)if(get(i) == i){
        vector <int> vc;
        for(int j = 0; j < n; j++){
            if(get(j) == i){
                vc.p_b(j);
                for(int i1 = 0; i1 < n; i1++)if(p[j][i1] == 2){
                    if(get(i1) == get(j))return 0;
                    mb[i][i1] = 1;
                }
            }
        }
        for(int j = 1; j < sz(vc); j++){
            answer[vc[j - 1]][vc[j]] = answer[vc[j]][vc[j - 1]] = 1;
        }
        for(int j = 0; j < n; j++)if(mb[i][j]){
            if(get1(get(j)) != get1(i)){
                p2[get1(get(j))] = get1(i);
            }
        }
    }
    for(int i = 0; i < n; i++)if(get1(i) == i){
        vector <int> vc;
        for(int j = 0; j < n; j++)if(get(j) == j){
            if(get1(j) == i)vc.p_b(j);
        }
        if(!sz(vc))continue;
        if(sz(vc) == 2)return 0;
        for(int j = 1; j < sz(vc); j++){
            answer[vc[j - 1]][vc[j]] = answer[vc[j]][vc[j - 1]] = 1;
        }
        if(sz(vc) != 1){
            answer[vc[0]][vc.back()] = answer[vc.back()][vc[0]] = 1;
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int m = 0;
            if(get(i) == get(j))m = 1;
            if(get(i) == get(j))m = 2;
            if(m != p[i][j] && msk != 7)return 0;
        }
    }
    iota(p1, p1 + n, 0);
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(answer[i][j] && get(i) != get(j)){
                p1[get(i)] = get(j);
            }
        }
    }

    for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++){
        if(p[i][j] && get(i) != get(j))return 0;
        if(!p[i][j] && get(i) == get(j))return 0;
    }
    build(answer);
    return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 0 ms 256 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 0 ms 256 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB Answer gives possible 0 while actual possible 1
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 1 ms 256 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 0 ms 256 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 0 ms 256 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -