| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 770945 | OrazB | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second
int find(int i, vector<vector<int>> p){
set<int> s;
for (int j = 0; j < n; j++){
if (p[i][j] and i != j) s.insert(p[i][j]);
}
if (s.size() > 1) return -1;
if (!s.size()) return -2;
return *s.begin();
}
int construct(vector<vector<int>> p){
int n = p.size();
vector<vector<int>> b(n+1, vector<int>(n+1, 0));
vector<int> vis(n+1, 0);
for (int i = 0; i < n; i++){
if (vis[i]) continue;
int x = find(i, p);
if (x == -1) return 0;
if (x == -2) continue;
vector<int> vec;
for (int j = 0; j < n; j++){
if (p[i][j] and i != j) b[i][j] = b[j][i] = vis[j] = 1;
else if (!p[i][j]) vec.pb(j);
}
for (int j = 0; j < n; j++){
if (!p[i][j] or i == j) continue;
for (auto k : vec) if (p[j][k]) return 0;
}
if (x == 2){
int a1 = -1, b1 = -1;
for (int j = 0; j < n; j++){
if (p[i][j] and i != j){
if (a1 == -1) a1 = j;
else b1 = j;
}
}
if (b1 == -1) return 0;
b[a1][b1] = b[b1][a1] = 1;
}
}
build(b);
return 1;
}
// int main ()
// {
// }