oj.uz

Submission #627438

# Submission time Handle Problem Language Result Execution time Memory
627438 2022-08-12T15:06:19 Z ttamx Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 236 ms 23964 KB 
#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> ans;
vector<int> adj[1005];
int pa[1005];
bool vis[1005];

int fp(int u){
    if(pa[u]==u)return u;
    return pa[u]=fp(pa[u]);
}

void dfs(int u,int p){
    for(auto v:adj[u]){
        if(vis[v])continue;
        vis[v]=1;
        ans[u][v]=1;
        ans[v][u]=1;
        dfs(v,u);
    }
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	for(int i=0;i<n;++i)pa[i]=i;
	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(p[i][j]==3)return 0;
            if(p[i][j]==1){
                pa[fp(i)]=fp(j);
            }
            if(p[i][j]==2){
                adj[i].emplace_back(j);
            }
        }
	}
	for(int i=0;i<n;++i){
        dfs(i,-1);
        if(i==fp(i))continue;
        ans[i][fp(i)]=1;
        ans[fp(i)][i]=1;
	}
	/*
	for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
	}
	*/
	build(ans);
	return 1;
}
/*
int main(){
    int n;
    vector<vector<int>> p;
    cin >> n;
    p.resize(n);
    for(int i=0;i<n;++i){
        p[i].resize(n);
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin >> p[i][j];
        }
    }
    construct(p);
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 1236 KB Output is correct
7 Correct 209 ms 23964 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 1236 KB Output is correct
7 Correct 209 ms 23964 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 236 ms 23940 KB Output is correct
14 Incorrect 1 ms 212 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 1 ms 212 KB Output is correct
2 Correct 1 ms 328 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 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Too few ways to get from 0 to 1, should be 2 found 1
3 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 1236 KB Output is correct
7 Correct 209 ms 23964 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 236 ms 23940 KB Output is correct
14 Incorrect 1 ms 212 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 1236 KB Output is correct
7 Correct 209 ms 23964 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 1236 KB Output is correct
13 Correct 236 ms 23940 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -