oj.uz

Submission #1080096

# Submission time Handle Problem Language Result Execution time Memory
1080096 2024-08-29T06:58:30 Z GrindMachine Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 159 ms 24200 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);
			}
		}
	}

	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];
		rep(i,sz(nodes)){
			rep(j,i){
				int u = nodes[i], v = nodes[j];
				if(a[u][v] == 1){
					merge(u,v);
				}
			}
		}
		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 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 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 6 ms 1188 KB Output is correct
7 Correct 135 ms 24148 KB Output is correct

Subtask #2
0 / 10.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 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 6 ms 1188 KB Output is correct
7 Correct 135 ms 24148 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 1372 KB Output is correct
13 Correct 121 ms 24148 KB Output is correct
14 Incorrect 0 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 348 KB Output is correct
2 Correct 0 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 31 ms 6424 KB Output is correct
5 Correct 127 ms 24012 KB Output is correct
6 Correct 122 ms 24072 KB Output is correct
7 Correct 151 ms 23944 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 31 ms 6296 KB Output is correct
10 Correct 142 ms 24092 KB Output is correct
11 Correct 159 ms 24072 KB Output is correct
12 Correct 139 ms 24144 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 30 ms 6280 KB Output is correct
17 Correct 128 ms 24148 KB Output is correct
18 Correct 122 ms 24200 KB Output is correct
19 Correct 115 ms 24144 KB Output is correct
20 Correct 118 ms 24000 KB Output is correct

Subtask #5
0 / 21.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 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 6 ms 1188 KB Output is correct
7 Correct 135 ms 24148 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 1372 KB Output is correct
13 Correct 121 ms 24148 KB Output is correct
14 Incorrect 0 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 348 KB Output is correct
2 Correct 1 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 440 KB Output is correct
6 Correct 6 ms 1188 KB Output is correct
7 Correct 135 ms 24148 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 1372 KB Output is correct
13 Correct 121 ms 24148 KB Output is correct
14 Incorrect 0 ms 348 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -