oj.uz

답안 #779188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779188 2023-07-11T08:50:18 Z jasmin 슈퍼트리 잇기 (IOI20_supertrees) C++17
0 / 100
 156 ms 22532 KB 
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;

/*void build(vector<vector<int> > adi){
        int n=adi.size();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cout << adi[i][j] << " ";
            }
            cout << "\n";
        }
}*/

vector<vector<int> > components(vector<vector<int> >& p, int n, bool& pos){
    vector<vector<int> > comp;

    vector<bool> vis(n);
    vector<int> comp_num(n, -1); int mom=0;
    for(int v=0; v<n; v++){
        if(vis[v]) continue;
        vis[v]=true;

        comp.push_back({});
        comp.back().push_back(v);
        comp_num[v]=mom;

        for(int u=0; u<n; u++){
            if(u!=v && p[v][u]!=0){

                comp.back().push_back(u);
                comp_num[u]=mom;
            }
        }
        mom++;
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){

            if(comp_num[i]==comp_num[j]){
                pos = pos && (p[i][j]!=0 && p[j][i]!=0);
            }
            else{
                pos = pos && (p[i][j]==0 && p[j][i]==0);
            }

        }
    }
    
    return comp;
}

void solve_component(vector<int>& c, int n, vector<vector<int> >& p, vector<vector<int> >& adi, bool& pos){

    vector<int> cycle;
    vector<bool> vis(n);
    for(auto v: c){
        if(vis[v]) continue;

        cycle.push_back(v);
        for(auto u: c){

            if(u!=v && p[v][u]==1){
                adi[v][u]=1;
                adi[u][v]=1;

                vis[u]=true;

                for(int i=0; i<n; i++){
                    pos = pos && (p[v][i] == p[u][i]);
                }
            }
        }
    }

    for(int i=0; i+1<(int)cycle.size(); i++){
        adi[cycle[i]][cycle[i+1]]=1;
        adi[cycle[i+1]][cycle[i]]=1;
    }
    if(cycle.size()>1){
        adi[cycle[0]][cycle.back()]=1;
        adi[cycle.back()][cycle[0]]=1;
    }

    if(cycle.size()==2){
        pos=false;
    }
}

int construct(vector<vector<int> > p) {
	int n = p.size();
	
    bool pos=true;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==3){
                pos=false;
            }
        }
    }
	
	vector<vector<int> > comp=components(p, n, pos);


    vector<vector<int> > adi(n, vector<int> (n, 0));
    for(auto c: comp){
        solve_component(c, n, p, adi, pos);
    }

    if(pos){
        build(adi);
        return 1;
    }
    return 0;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int> > p(n, vector<int> (n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> p[i][j];
        }
    }

    cout << construct(p) << "\n";
}*/

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 232 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 232 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 7 ms 1188 KB Output is correct
9 Correct 156 ms 22532 KB Output is correct
10 Incorrect 1 ms 212 KB Too many ways to get from 0 to 3, should be 2 found no less than 3
11 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 232 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 232 KB Output is correct
3 Incorrect 0 ms 212 KB Too many ways to get from 0 to 2, should be 1 found no less than 2
4 Halted 0 ms 0 KB -