oj.uz

Submission #745931

# Submission time Handle Problem Language Result Execution time Memory
745931 2023-05-21T09:45:20 Z JakobZorz Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 212 ms 24012 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);
                    break;
                }
            }
            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:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int j=0;j<groups[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~~~

Subtask #1
11.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 189 ms 22032 KB Output is correct

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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 189 ms 22032 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 9 ms 1260 KB Output is correct
13 Correct 212 ms 22360 KB Output is correct
14 Incorrect 0 ms 316 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.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 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 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 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 48 ms 6272 KB Output is correct
5 Correct 195 ms 23944 KB Output is correct
6 Correct 181 ms 24012 KB Output is correct
7 Correct 210 ms 23984 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 50 ms 6212 KB Output is correct
10 Correct 197 ms 23976 KB Output is correct
11 Correct 188 ms 23932 KB Output is correct
12 Correct 197 ms 23940 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 47 ms 6268 KB Too few ways to get from 0 to 39, should be 2 found 0
17 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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 189 ms 22032 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 9 ms 1260 KB Output is correct
13 Correct 212 ms 22360 KB Output is correct
14 Incorrect 0 ms 316 KB Answer gives possible 1 while actual possible 0
15 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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct
7 Correct 189 ms 22032 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 9 ms 1260 KB Output is correct
13 Correct 212 ms 22360 KB Output is correct
14 Incorrect 0 ms 316 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -