| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1239475 | Sir_Ahmed_Imran | Carnival Tickets (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
bool po;
int cc[MAXN];
int par[MAXN];
bool vis[MAXN];
int a[MAXN][MAXN];
vector<int> e[MAXN];
vector<vector<int>> ans;
void get(vector<int> v){
if(!v.size()) return;
bool c;
vector<int> u, t, l;
for(auto & i : v){
c = 1;
vis[i] = 0;
for(auto & j : u){
if(a[i][j] == 0){
if(j != u[0]){
po = 0;
return;
}
l.append(i);
vis[i] = 1;
c = 0;
}
if(a[i][j] == 1){
t.append(i);
par[i] = j;
cc[i] = u[0];
c = 0;
}
}
if(c){
t.append(i);
u.append(i);
par[i] = i;
cc[i] = u[0];
}
}
int n = u.size();
if(n == 2){
po = 0;
return;
}
if(n == 1) n = 0;
for(int i = 0; i < n; i++){
ans[u[i]][u[(i + 1) % n]] = 1;
ans[u[(i + 1) % n]][u[i]] = 1;
}
get(l);
}
int construct(vector<vector<int>> p){
int n = p[0].size();
vector<int> v, u;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
a[i][j] = p[i][j];
if(p[i][j] != p[j][i])
return 0;
}
v.append(i);
u.append(0);
}
for(int i = 0; i < n; i++)
ans.append(u);
po = 1;
get(v);
if(!po) return 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(cc[i] != cc[j]){
if(a[i][j] != 0)
return 0;
}
else if(par[i] == par[j]){
if(a[i][j] != 1){
return 0;
}
if(i != par[i]){
ans[i][par[i]] = 1;
ans[par[i]][i] = 1;
}
}
else if(a[i][j] != 2)
return 0;
}
}
build(ans);
return 1;
}