oj.uz

Submission #1052255

# Submission time Handle Problem Language Result Execution time Memory
1052255 2024-08-10T12:47:57 Z inesfi Connecting Supertrees (IOI20_supertrees) C++14
46 / 100
 155 ms 32128 KB 
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;

const int TAILLEMAXI=1002;
int nbpers,couleur,pb;
int dejavu[TAILLEMAXI];
int num[TAILLEMAXI];
int nbchem[TAILLEMAXI][TAILLEMAXI];
vector<int> ec;
vector<int> compo[TAILLEMAXI];
vector<int> un[TAILLEMAXI];
int rep[TAILLEMAXI][TAILLEMAXI];
vector<vector<int>> r;
vector<int> deux;

void dfs1(int n){
    if (dejavu[n]==1){
        return ;
    }
    dejavu[n]=1;
    num[n]=couleur;
    ec.push_back(n);
    for (int i=0;i<nbpers;i++){
        if (nbchem[n][i]>0){
            dfs1(i);
        }
    }
}

void dfs2(int n){
    if (dejavu[n]==1){
        return ;
    }
    dejavu[n]=1;
    ec.push_back(n);
    for (int i=0;i<nbpers;i++){
        if (nbchem[n][i]==1){
            dfs2(i);
        }
    }
}

int construct(vector<vector<int>> c) {
	nbpers=c.size();
    for (int i=0;i<nbpers;i++){
        for (int j=0;j<nbpers;j++){
            nbchem[i][j]=c[i][j];
        }
    }
    for (int i=0;i<nbpers;i++){
        if (dejavu[i]==0){
            ec.clear();
            dfs1(i);
            compo[couleur]=ec;
            couleur++;
        }
    }
    for (int j=0;j<nbpers;j++){
        dejavu[j]=0;
    }
    for (int i=0;i<couleur;i++){
        deux.clear();
        for (int ipers=0;ipers<(int)compo[i].size();ipers++){
            if (dejavu[compo[i][ipers]]==0){
                deux.push_back(compo[i][ipers]);
            }
            ec.clear();
            dfs2(compo[i][ipers]);
            un[compo[i][ipers]]=ec;
            if (ec.size()>1) {
                for (int ilien=0;ilien<(int)un[compo[i][ipers]].size()-1;ilien++){
                    rep[un[compo[i][ipers]][ilien]][un[compo[i][ipers]][ilien+1]]=1;
                    rep[un[compo[i][ipers]][ilien+1]][un[compo[i][ipers]][ilien]]=1;
                }
            }
        }
        for (int ideux=0;ideux<(int)deux.size()-1;ideux++){
            rep[deux[ideux]][deux[ideux+1]]=1;
            rep[deux[ideux+1]][deux[ideux]]=1;
        }
        if (deux.size()>2){
            rep[deux[0]][deux[deux.size()-1]]=1;
            rep[deux[deux.size()-1]][deux[0]]=1;
        }
    }
    for (int i=0;i<nbpers;i++){
        ec.clear();
        for (int j=0;j<nbpers;j++){
            if (rep[i][j]==1){
                ec.push_back(1);
            }
            else {
                ec.push_back(0);
            }
        }
        r.push_back(ec);
    }
	build(r);
	return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2496 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 155 ms 32128 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2496 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 155 ms 32128 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 5 ms 5316 KB Output is correct
13 Correct 130 ms 29716 KB Output is correct
14 Incorrect 0 ms 2396 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Incorrect 0 ms 2652 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 24 ms 12640 KB Output is correct
5 Correct 99 ms 32016 KB Output is correct
6 Correct 100 ms 31824 KB Output is correct
7 Correct 130 ms 31896 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 25 ms 12580 KB Output is correct
10 Correct 98 ms 32020 KB Output is correct
11 Correct 142 ms 31764 KB Output is correct
12 Correct 108 ms 32084 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2496 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 25 ms 12636 KB Output is correct
17 Correct 100 ms 31916 KB Output is correct
18 Correct 97 ms 32084 KB Output is correct
19 Correct 97 ms 32080 KB Output is correct
20 Correct 104 ms 31828 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2496 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 155 ms 32128 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 5 ms 5316 KB Output is correct
13 Correct 130 ms 29716 KB Output is correct
14 Incorrect 0 ms 2396 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 1 ms 2496 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 155 ms 32128 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 5 ms 5316 KB Output is correct
13 Correct 130 ms 29716 KB Output is correct
14 Incorrect 0 ms 2396 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -