Submission #301900

#	Time	Username	Problem	Language	Result	Execution time	Memory
301900		Pro100Yan	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	384 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;
const int N = 2005;
vector<vector<int>> ans;
int d[N], used[N];

int get_parent(int v){
    if(v == d[v])
      	return v;
    return d[v] = get_parent(d[v]);
}

void add(int u, int v){
    int f = get_parent(u), s = get_parent(v);
    if(f != s)
        d[f] = d[s];
}



int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	vector<int> comps[N];
	set<int> ds;
	int fault = 0;
	for(int i = 0; i < n; i++)
        d[i] = i;
	for (int i = 0; i < n; i++) {
		std::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]){
                add(i, j);
            }
        }
    }
    int pi, pj;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            pi = get_parent(i);
            pj = get_parent(j);
            if(p[i][j]){
                if(pi != pj)
                    return 0;
                ds.insert(pi);
                if(i < j){
                    if(i != pi)
                        comps[pi].pb(i);
                    else if(j != pi)
                        comps[pi].pb(j);
                }
            }
            else{
                if(pi == pj)
                    return 0;
            }
        }

    }
    int sz;
    for(auto& e : ds){
        sz = comps[e].size();
        if(sz <= 1)
            return 0;
        ans[e][comps[e][0]] = ans[comps[e][0]][e] = 1;
        for(int i = 1; i < sz; i++)
            ans[comps[e][i]][comps[e][i - 1]] = ans[comps[e][i - 1]][comps[e][i]] = 1;
        ans[comps[e][sz - 1]][e] = ans[e][comps[e][sz - 1]] = 1;
    }
    for(int i = 0; i < n; i++)
        ans[i][i] = 0;
	build(ans);
	return 1;
}
/*
5
1 1 0 0 0
1 1 0 0 0
0 0 1 2 2
0 0 2 1 2
0 0 2 2 1
3
1 2 0
2 1 0
0 0 0

4
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 1
*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:78:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |     for(int i = 0; i < n; i++)
      |     ^~~
supertrees.cpp:80:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |  build(ans);
      |  ^~~~~
supertrees.cpp:29:6: warning: unused variable 'fault' [-Wunused-variable]
   29 |  int fault = 0;
      |      ^~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4