oj.uz

Submission #956568

# Submission time Handle Problem Language Result Execution time Memory
956568 2024-04-02T07:17:29 Z KK_1729 Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 171 ms 24180 KB 
#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
struct UFDS {
    vector<int> link, siz;
    UFDS(int n) : link(n), siz(n, 1) { iota(link.begin(), link.end(), 0); } //each element as its own subset, with size 1
    int findRoot(int x) {
        if(x == link[x]) return x;
        return link[x] = findRoot(link[x]);
        /*
        A shorter way of writing the following is:
        return x == link[x]  ? x : link[x]  =  findRoot(link[x]);  
        */
    }
    bool same(int x, int y) { return findRoot(x) == findRoot(y); }
    bool unite(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y)
            return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        link[y] = x;
        return true;
    }
    int size(int x) { return siz[findRoot(x)]; }
};


int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}


	UFDS ds(n);
	vector<int> cycle(n);
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (i == j) continue;
			if (p[i][j] == 2){
				ds.unite(i, j);
				cycle[i] = 1;
			}
			if (p[i][j] == 1){
				cycle[i] = 0;
				ds.unite(i, j);
			}
		}
	}


	vector<vector<int>> parents(n);

	for (int i = 0; i < n; ++i) parents[ds.findRoot(i)].push_back(i);
	
	for (auto item: parents){
		int u = item.size();
		vector<int> cyc;
		vector<int> normal;
		for (auto x: item){
			if (cycle[x]) cyc.pb(x);
			else normal.pb(x);
		}

		int v = normal.size();
		FOR(i,0,v-1){
			answer[normal[i]][normal[i+1]] = 1;
			answer[normal[i+1]][normal[i]] = 1;
		}

		// if (cyc.size() <= 2) return 0;
		if (cyc.size()){
			if (normal.size()) cyc.pb(normal[0]);
			v = cyc.size();

			FOR(i,0,v-1){

				answer[cyc[i]][cyc[i+1]] = 1;
				answer[cyc[i+1]][cyc[i]] = 1;
			}
			answer[cyc[0]][cyc[v-1]] = 1;
			answer[cyc[v-1]][cyc[0]] = 1;

			
		}
	}
	build(answer);
	return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:65:7: warning: unused variable 'u' [-Wunused-variable]
   65 |   int u = item.size();
      |       ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 161 ms 23636 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 161 ms 23636 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 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 1364 KB Output is correct
13 Correct 155 ms 23464 KB Output is correct
14 Incorrect 1 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 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 1 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 50 ms 6408 KB Output is correct
5 Correct 165 ms 24180 KB Output is correct
6 Correct 171 ms 24072 KB Output is correct
7 Correct 156 ms 23980 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 38 ms 6224 KB Output is correct
10 Correct 154 ms 24016 KB Output is correct
11 Correct 153 ms 24052 KB Output is correct
12 Correct 162 ms 24172 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 1 ms 344 KB Too many ways to get from 0 to 4, should be 1 found no less than 2
16 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 161 ms 23636 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 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 1364 KB Output is correct
13 Correct 155 ms 23464 KB Output is correct
14 Incorrect 1 ms 348 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 161 ms 23636 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 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 1364 KB Output is correct
13 Correct 155 ms 23464 KB Output is correct
14 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -