oj.uz

Submission #745964

# Submission time Handle Problem Language Result Execution time Memory
745964 2023-05-21T10:10:44 Z JakobZorz Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 320 KB 
#include "supertrees.h"
#include <vector>
using namespace std;

vector<vector<int>> answer;
int group_ids[1000];
vector<int> groups[1000];

void connect(int a, int b){
    answer[a][b]=1;
    answer[b][a]=1;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	answer=vector<vector<int>>(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
        group_ids[i]=-1;
    
    int curr_group=0;
    for(int i=0;i<n;i++){
        if(group_ids[i]!=-1)
            continue;
        group_ids[i]=curr_group;
        groups[curr_group].push_back(i);
        for(int j=i+1;j<n;j++){
            if(group_ids[j]!=-1)
                continue;
            bool valid=true;
            for(int node:groups[curr_group]){
                if(p[node][j]!=2){
                    valid=false;
                    break;
                }
            }
            
            if(valid){
                group_ids[j]=curr_group;
                groups[curr_group].push_back(j);
            }
        }
        curr_group++;
    }
    
    /*for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]==2&&group_ids[i]!=group_ids[j])
                return 0;
            if(p[i][j]==0&&group_ids[i]==group_ids[j])
                return 0;
        }
    }*/
    
    for(int i=0;i<curr_group;i++){
        if(groups[i].size()==1){
            int curr=groups[i][0];
            for(int j=0;j<n;j++){
                if(j==curr)
                    continue;
                if(p[curr][j]==1){
                    connect(curr,j);
                }
            }
            continue;
        }
        /*if(groups[i].size()==2)
            return 0;*/
        for(int j=0;j<groups[i].size()-1;j++){
            connect(groups[i][j],groups[i][j+1]);
        }
        connect(groups[i][0],groups[i].back());
    }
    
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j=0;j<groups[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 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

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 320 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 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 -