oj.uz

Submission #1080098

# Submission time Handle Problem Language Result Execution time Memory
1080098 2024-08-29T07:01:50 Z GrindMachine Connecting Supertrees (IOI20_supertrees) C++17
56 / 100
 149 ms 24208 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; ++i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
    return "'"+s+"'";
}

string to_string(const char* s){
    return to_string((string)s);
}

string to_string(bool b){
    return b?"true":"false";
}

template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "supertrees.h"

vector<int> par(N);

void create(int n){
	rep(i,n) par[i] = i;
}

int find(int u){
	if(u == par[u]) return u;
	else return par[u] = find(par[u]);
}

void merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return;
	par[v] = u;
}

int construct(std::vector<std::vector<int>> a) {
	int n = a.size();
	vector<vector<int>> ans(n,vector<int>(n));
	create(n);

	rep(i,n){
		rep(j,n){
			if(a[i][j]){
				merge(i,j);
			}
		}
	}

	rep(i,n){
		rep(j,n){
			int x = a[i][j] > 0;
			int y = find(i) == find(j);
			if(x != y){
				return 0;
			}
		}
	}

	vector<int> group[n];
	rep(i,n) group[find(i)].pb(i);

	auto f = [&](int u, int v){
		ans[u][v] = ans[v][u] = 1;
	};

	rep(c,n){
		auto &nodes = group[c];
		if(nodes.empty()) conts;
		create(n);
		vector<int> cc[n];
		trav(u,nodes){
			trav(v,nodes){
				if(a[u][v] == 1){
					merge(u,v);
				}
			}
		}

		trav(u,nodes){
			trav(v,nodes){
				int x = a[u][v] == 1;
				int y = find(u) == find(v);
				if(x != y){
					return 0;
				}
			}
		}

		trav(u,nodes){
			cc[find(u)].pb(u);
		}

		vector<int> cyc;

		rep(id,n){
			if(cc[id].empty()) conts;
			auto &curr = cc[id];
			cyc.pb(curr[0]);
			rep(i,sz(curr)-1){
				f(curr[i],curr[i+1]);
			}
		}

		int siz = sz(cyc);
		if(siz > 1){
			rep(i,siz){
				f(cyc[i],cyc[(i+1)%siz]);
			}
		}
	}

	build(ans);
	return 1;

	// std::vector<std::vector<int>> answer;
	// for (int i = 0; i < n; i++) {
	// 	std::vector<int> row;
	// 	row.resize(n);
	// 	answer.push_back(row);
	// }
	// build(answer);
	// return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 132 ms 22032 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 132 ms 22032 KB Output is correct
8 Correct 1 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 5 ms 1116 KB Output is correct
13 Correct 123 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 75 ms 14160 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 30 ms 6396 KB Output is correct
21 Correct 128 ms 24148 KB Output is correct
22 Correct 118 ms 24072 KB Output is correct
23 Correct 131 ms 23948 KB Output is correct
24 Correct 126 ms 24144 KB Output is correct
25 Correct 52 ms 14160 KB Output is correct
26 Correct 54 ms 14220 KB Output is correct
27 Correct 149 ms 24208 KB Output is correct
28 Correct 126 ms 24144 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 34 ms 5780 KB Output is correct
5 Correct 118 ms 22044 KB Output is correct
6 Correct 119 ms 22100 KB Output is correct
7 Correct 133 ms 22024 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 41 ms 5884 KB Output is correct
10 Correct 120 ms 22200 KB Output is correct
11 Correct 115 ms 22032 KB Output is correct
12 Correct 130 ms 22352 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 31 ms 5716 KB Output is correct
17 Correct 126 ms 22096 KB Output is correct
18 Correct 124 ms 22036 KB Output is correct
19 Correct 121 ms 22096 KB Output is correct
20 Correct 122 ms 22096 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 132 ms 22032 KB Output is correct
8 Correct 1 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 5 ms 1116 KB Output is correct
13 Correct 123 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 75 ms 14160 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 30 ms 6396 KB Output is correct
21 Correct 128 ms 24148 KB Output is correct
22 Correct 118 ms 24072 KB Output is correct
23 Correct 131 ms 23948 KB Output is correct
24 Correct 126 ms 24144 KB Output is correct
25 Correct 52 ms 14160 KB Output is correct
26 Correct 54 ms 14220 KB Output is correct
27 Correct 149 ms 24208 KB Output is correct
28 Correct 126 ms 24144 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 132 ms 22032 KB Output is correct
8 Correct 1 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 5 ms 1116 KB Output is correct
13 Correct 123 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 75 ms 14160 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 30 ms 6396 KB Output is correct
21 Correct 128 ms 24148 KB Output is correct
22 Correct 118 ms 24072 KB Output is correct
23 Correct 131 ms 23948 KB Output is correct
24 Correct 126 ms 24144 KB Output is correct
25 Correct 52 ms 14160 KB Output is correct
26 Correct 54 ms 14220 KB Output is correct
27 Correct 149 ms 24208 KB Output is correct
28 Correct 126 ms 24144 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -