oj.uz

Submission #953762

# Submission time Handle Problem Language Result Execution time Memory
953762 2024-03-26T15:37:11 Z Trisanu_Das Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 175 ms 24148 KB 
#include "supertrees.h"
#include <vector>
 
using namespace std;
 
int par[1005];
 
int fi(int i){
    if(par[i]==i)
        return i;
    else
        return par[i]=fi(par[i]);
}
 
void un(int i,int j){
    par[fi(j)]=fi(i);
}
 
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
 
	for(int i=0;i<n;i++)
        par[i]=i;
 
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]==1&&fi(i)!=fi(j)){
                ans[i][j]=ans[j][i]=1;
                un(i,j);
            }
            if(p[i][j]==3||(p[i][j]==0&&fi(i)==fi(j)))
                return 0;
        }
    }
 
    for(int i=0;i<n;i++){
        vector<int> v;
        v.push_back(par[i]);
 
        for(int j=i+1;j<n;j++){
            if(p[i][j]==2&&fi(i)!=fi(j)){
                v.push_back(par[j]);
                un(i,j);
            }
        }
 
        if(v.size()==2)
            return 0;
 
        for(int k=0;k+1<v.size();k++)
            ans[v[k]][v[k+1]]=ans[v[k+1]][v[k]]=1;
        ans[v[0]][v[v.size()-1]]=ans[v[v.size()-1]][v[0]]=1;
 
    }
 
    for(int i=0;i<n;i++)
        ans[i][i]=0;
 
	build(ans);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int k=0;k+1<v.size();k++)
      |                     ~~~^~~~~~~~~
supertrees.cpp:62:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   62 |     for(int i=0;i<n;i++)
      |     ^~~
supertrees.cpp:65:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |  build(ans);
      |  ^~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 140 ms 22116 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 140 ms 22116 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 170 ms 22100 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 62 ms 12044 KB Output is correct
18 Incorrect 1 ms 344 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 133 ms 22028 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 142 ms 22032 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
16 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 34 ms 6276 KB Output is correct
5 Correct 166 ms 24088 KB Output is correct
6 Correct 143 ms 23888 KB Output is correct
7 Correct 143 ms 24132 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 35 ms 6236 KB Output is correct
10 Correct 139 ms 23936 KB Output is correct
11 Correct 137 ms 23888 KB Output is correct
12 Correct 163 ms 24096 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 34 ms 6244 KB Output is correct
17 Correct 140 ms 24148 KB Output is correct
18 Correct 175 ms 23932 KB Output is correct
19 Correct 143 ms 24048 KB Output is correct
20 Correct 159 ms 23888 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 140 ms 22116 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 170 ms 22100 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 62 ms 12044 KB Output is correct
18 Incorrect 1 ms 344 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 140 ms 22116 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 170 ms 22100 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 62 ms 12044 KB Output is correct
18 Incorrect 1 ms 344 KB Answer gives possible 1 while actual possible 0
19 Halted 0 ms 0 KB -