Submission #437662

#	Time	Username	Problem	Language	Result	Execution time	Memory
437662		xiaowuc1	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	282 ms	23964 KiB

supertrees

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
#include "supertrees.h"

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
// END NO SAD
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;
 
int find(vector<int>& p, int x) {
  return p[x] == x ? x : (p[x] = find(p, p[x]));
}
void merge(vector<int>& p, int x, int y) {
  p[find(p, x)] = find(p, y);
}
 
int construct(vector<vector<int>> p) {
  int n = sz(p);
  vector<vector<int>> ret;
  for(int i = 0; i < n; i++) {
    vector<int> t(n);
    ret.pb(t);
  }
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 3) return 0;
  vector<int> connectedcomponent(n);
  iota(all(connectedcomponent), 0);
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j]) merge(connectedcomponent, i, j);
  // check zero
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 0 && find(connectedcomponent, i) == find(connectedcomponent, j)) return 0;
  // check one
  vector<int> oneedge(n);
  iota(all(oneedge), 0);
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 1) merge(oneedge, i, j);
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] != 1 && find(oneedge, i) != find(oneedge, j)) return 0; 
  map<int, int> treetoroot;
  for(int i = 0; i < n; i++) {
    if(!treetoroot.count(find(oneedge, i))) {
      treetoroot[find(oneedge, i)] = i;
    }
    else {
      ret[treetoroot[find(oneedge, i)]][i] = 1;
      ret[i][treetoroot[find(oneedge, i)]] = 1;
    }
  }
  map<int, set<int>> roots;
  for(int i = 0; i < n; i++) {
    roots[find(connectedcomponent, i)].insert(treetoroot[find(oneedge, i)]);
  }
  for(auto out: roots) {
    if(sz(out.s) == 2) return 0;
    if(sz(out.s) == 1) continue;
    vector<int> v(all(out.s));
    for(int i = 0; i < sz(v); i++) {
      int j = (i+1)%sz(v);
      ret[v[i]][v[j]] = 1;
      ret[v[j]][v[i]] = 1;
    }
  }
  build(ret);
  return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4