oj.uz

Submission #804314

# Submission time Handle Problem Language Result Execution time Memory
804314 2023-08-03T07:59:11 Z Warinchai Connecting Supertrees (IOI20_supertrees) C++14
19 / 100
 197 ms 27972 KB 
#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int sz;
vector<vector<int> >v;
vector<vector<int> >ans;
int pr[1005];
int in[1005];
int fp(int a){
    if(pr[a]==a){
        return a;
    }
    return pr[a]=fp(pr[a]);
}
void un(int a,int b){
    if(fp(a)!=fp(b)){
        ans[a][b]=1;
        ans[b][a]=1;
        pr[fp(b)]=fp(a);
    }
}
bool build_1(){
    for(int i=0;i<sz;i++){
        for(int j=i+1;j<sz;j++){
            if(v[i][j]==1){
                un(i,j);
            }
        }
    }
    return 1;
}
int use_2[1005];
bool build_2(){
    for(int i=0;i<sz;i++){
        if(in[i]==1){
            for(int j=0;j<sz;j++){
                if(v[i][j]==2&&fp(i)!=fp(j)){
                    return 0;
                }
                if(v[i][j]==0&&fp(i)==fp(j)){
                    return 0;
                }
            }
            continue;
        }
        int en=i;
        int count=0;
        for(int j=0;j<sz;j++){
            if(v[i][j]==2){
                if(in[j]==1){
                    return 0;
                }
                un(en,j);
                in[en]=1;
                in[j]=1;
                en=j;
                count++;
            }
        }
        if(count==1){
            return 0;
        }
        if(count!=0){
            ans[i][en]=1;
            ans[en][i]=1;
        }
    }
    return 1;
}
bool check_0(){
    for(int i=0;i<sz;i++){
        for(int j=i+1;j<sz;j++){
            if(v[i][j]==0&&fp(i)==fp(j))return 0;
        }
    }
    return 1;
}
int construct(vector<vector<int> > p) {
    //cout<<"work"<<endl;
	sz = p.size();
    bool check=0;
    v.resize(sz);
    for(int i=0;i<sz;i++){
        v[i].resize(sz);
    }
    for(int i=0;i<sz;i++){
        for(int j=0;j<sz;j++){
            //cout<<"i j "<<i<<" "<<j<<endl;
            v[i][j]=p[i][j];
            if(p[i][j]!=p[j][i]||(i==j&&p[i][j]!=1)){
                check=1;
                //cout<<"break"<<endl;
                break;
            }
        }
    }
    //cout<<"work"<<endl;
    if(check){
        return 0;
    }
    //cout<<"work"<<endl;
    ans.resize(sz);
    for(int i=0;i<sz;i++){
        ans[i].resize(sz);
    }
    for(int i=0;i<sz;i++){
        pr[i]=i;
    }
    //cout<<"work"<<endl;
    if(!build_2()){
        //cout<<"break 2"<<endl;
        return 0;
    }
    /*if(!build_1()){
        cout<<"break 1"<<endl;
        return 0;
    }*/
    if(!check_0()){
        //cout<<"break 0";
        return 0;
    }else{
        build(ans);
    }
	//cout<<"ans:"<<endl;
	return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 304 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 304 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 7 ms 1432 KB Output is correct
9 Correct 173 ms 27904 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1364 KB Output is correct
13 Correct 170 ms 27944 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 88 ms 18044 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 39 ms 7176 KB Output is correct
22 Correct 161 ms 27872 KB Output is correct
23 Correct 187 ms 27972 KB Output is correct
24 Correct 197 ms 27956 KB Output is correct
25 Correct 75 ms 18044 KB Output is correct
26 Correct 99 ms 18052 KB Output is correct
27 Correct 166 ms 27900 KB Output is correct
28 Correct 193 ms 27916 KB Output is correct
29 Correct 70 ms 17952 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 308 KB Too few ways to get from 1 to 2, should be 1 found 0
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 304 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 304 KB Too few ways to get from 0 to 1, should be 1 found 0
3 Halted 0 ms 0 KB -