Submission #807447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
807447	2023-08-04T17:42:56 Z	Boomyday	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	0 ms	212 KB

supertrees

//
// Created by adavy on 8/4/2023.
//
 
 
//
// Created by adavy on 2/12/2023.
//
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
 
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define tcT template<class T
#define tcTU tcT, class U
 
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
 
// pairs
#define mp make_pair
#define f first
#define s second
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
 
 
 
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include "supertrees.h"
/*
static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;
 
static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}
 
void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n, "Invalid number of rows in b");
    for (int i = 0; i < n; i++) {
        check((int)_b[i].size() == n, "Invalid number of columns in b");
    }
    b = _b;
}
*/
int N;
int construct(std::vector<std::vector<int>> P) {
    N = P.size();
    std::vector<std::vector<int>> answer(N,vi(N,0));
 
    struct DSU {
        vi anc;
 
        void init(int Size) {
            anc.rsz(Size);
            for (int i = 0; i < N; i++) {
                anc[i] = i;
            }
        }
 
        int fRt(int i) {
            return anc[i] == i ? i : anc[i] = fRt(anc[i]);
        }
 
        bool merge(int a, int o) {
            a = fRt(a), o = fRt(o);
            if (a == o) {
                return false;
            }
            anc[a] = o;
            return true;
        }
    };
 
    DSU dsu;
    dsu.init(N);
 
    F0R(i, N) F0R(j,N) if (P[i][j] > 1) dsu.merge(i,j);
    vector<vi> comps;
    vb vis(N);
    F0R(i,N){
        if (vis[i]) continue;
        vis[i] = 1;
        vi comp = {i};
        F0R(j,N) {
            if (j==i) continue;
            if (dsu.fRt(i)==dsu.fRt(j)) {
                vis[j] = 1;
                comp.pb(j);
            }
        }
        comps.pb(comp);
    }
 
    //cout << "cmp " << comps.size() << " " << comps[0].size() << endl;
 
 
 
 
    //cout << "foo" << endl;
 
    trav(comp,comps){
        trav(i,comp) trav(j,comp) {
            if (P[i][j]==0 or P[i][j]==3) return 0;
        }
    }
 
 
    //cout << "cmps" <<  comps.size() << endl;
 
    trav(comp,comps) F0R(i,comp.size()-1) {
        answer[comp[i]][comp[i+1]] = 1;
        answer[comp[i+1]][comp[i]] = 1;
    }
 
    build(answer);
    return 1;
}
 
/*
int main() {
    assert(scanf("%d", &n) == 1);
 
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[i].resize(n);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            assert(scanf("%d", &p[i][j]) == 1);
        }
    }
    fclose(stdin);
 
    int possible = construct(p);
 
    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }
 
    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}
*/

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:43:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
supertrees.cpp:44:18: note: in expansion of macro 'FOR'
   44 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
supertrees.cpp:164:22: note: in expansion of macro 'F0R'
  164 |     trav(comp,comps) F0R(i,comp.size()-1) {
      |                      ^~~

Subtask #1
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Too few ways to get from 0 to 1, should be 1 found 0
3	Halted	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Too few ways to get from 0 to 1, should be 1 found 0
3	Halted	0 KB	-

Subtask #3
0 / 19.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Incorrect	212 KB	Answer gives possible 1 while actual possible 0
5	Halted	0 KB	-