| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 746030 | 2023-05-21T10:40:13 Z | JakobZorz | Connecting Supertrees (IOI20_supertrees) | C++14 | 247 ms | 24080 KB |
#include "supertrees.h"
#include <vector>
using namespace std;
vector<vector<int>> answer;
int group_ids[1000];
vector<int> groups[1000];
int group_ids2[1000];
vector<int> groups2[1000];
bool vis[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;
group_ids2[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&&groups[group_ids[j]].size()!=1){
connect(curr,j);
vis[curr]=true;
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]);
vis[groups[i][j]]=true;
}
connect(groups[i][0],groups[i].back());
vis[groups[i].back()]=true;
}
int curr_group2=0;
for(int i=0;i<n;i++){
if(group_ids2[i]!=-1&&!vis[i])
continue;
group_ids2[i]=curr_group;
groups2[curr_group2].push_back(i);
for(int j=i+1;j<n;j++){
if(p[i][j]==1){
group_ids2[j]=curr_group2;
groups2[curr_group2].push_back(j);
}
}
curr_group2++;
}
for(int i=0;i<curr_group2;i++){
for(int j=0;j<groups2[i].size()-1;j++){
connect(groups2[i][j],groups2[i][j+1]);
}
}
build(answer);
return 1;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 14 ms | 1312 KB | Output is correct |
| 7 | Correct | 180 ms | 23228 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 14 ms | 1312 KB | Output is correct |
| 7 | Correct | 180 ms | 23228 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 8 ms | 1236 KB | Output is correct |
| 13 | Correct | 173 ms | 23936 KB | Output is correct |
| 14 | Incorrect | 1 ms | 340 KB | Answer gives possible 1 while actual possible 0 |
| 15 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 0 ms | 340 KB | Output is correct |
| 4 | Incorrect | 1 ms | 340 KB | Answer gives possible 1 while actual possible 0 |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 51 ms | 6220 KB | Output is correct |
| 5 | Correct | 247 ms | 24040 KB | Output is correct |
| 6 | Correct | 174 ms | 24072 KB | Output is correct |
| 7 | Correct | 190 ms | 24012 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 45 ms | 6308 KB | Output is correct |
| 10 | Correct | 197 ms | 24080 KB | Output is correct |
| 11 | Correct | 173 ms | 24068 KB | Output is correct |
| 12 | Correct | 174 ms | 23968 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 1 ms | 340 KB | Output is correct |
| 15 | Correct | 1 ms | 340 KB | Output is correct |
| 16 | Incorrect | 61 ms | 6200 KB | Too many ways to get from 0 to 278, should be 1 found no less than 2 |
| 17 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 14 ms | 1312 KB | Output is correct |
| 7 | Correct | 180 ms | 23228 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 8 ms | 1236 KB | Output is correct |
| 13 | Correct | 173 ms | 23936 KB | Output is correct |
| 14 | Incorrect | 1 ms | 340 KB | Answer gives possible 1 while actual possible 0 |
| 15 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 340 KB | Output is correct |
| 6 | Correct | 14 ms | 1312 KB | Output is correct |
| 7 | Correct | 180 ms | 23228 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 8 ms | 1236 KB | Output is correct |
| 13 | Correct | 173 ms | 23936 KB | Output is correct |
| 14 | Incorrect | 1 ms | 340 KB | Answer gives possible 1 while actual possible 0 |
| 15 | Halted | 0 ms | 0 KB | - |