Submission #576790

#	Time	Username	Problem	Language	Result	Execution time	Memory
576790		nghiass001	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	189 ms	27888 KiB

supertrees

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;

const int N = 1e3 + 5;
int nn, avail[N];
vector<vector<int>> adj;
vector<int> Q, List;

void build(vector<vector<int>> b);

void DFS(int u) {
    Q.push_back(u);
    avail[u] = 1;
    REP(v, 0, nn) if (adj[u][v] == 1 && avail[v] == 0)
        DFS(v);
}

void DFS2(int u) {
    Q.push_back(u);
    avail[u] = 1;
    for(int v : List) if (adj[u][v] == 2 && avail[v] == 0)
        DFS2(v);
}

void DFS3(int u) {
    Q.push_back(u);
    avail[u] = 1;
    for(int v : List) if (adj[u][v] == 3 && avail[v] == 0)
        DFS2(v);
}

int construct(vector<vector<int>> p) {
    adj = p;
    nn = p.size();
    vector<vector<int>> ans(nn, vector<int>(nn, 0));
    REP(i, 0, nn) if (avail[i] == 0) {
        Q.clear();
        DFS(i);
        for(int u : Q) if (p[i] != p[u]) return 0;
        REP(i, 1, Q.size()) ans[Q[i - 1]][Q[i]] = ans[Q[i]][Q[i - 1]] = 1;
        List.push_back(i);
    }
    fill(avail, avail + nn, 0);
    for(int i : List) if (avail[i] == 0) {
        Q.clear();
        DFS2(i);
        if (Q.size() == 1) continue;
        if (Q.size() == 2) return 0;
        for(int u : Q) for(int v : Q) if (u != v && adj[u][v] != 2) return 0;
        REP(i, 1, Q.size()) ans[Q[i - 1]][Q[i]] = ans[Q[i]][Q[i - 1]] = 1;
        ans[Q[0]][Q.back()] = ans[Q.back()][Q[0]] = 1;
    }
    fill(avail, avail + nn, 0);
    for(int i : List) if (avail[i] == 0) {
        Q.clear();
        DFS3(i);
        if (Q.size() == 1) continue;
        if (Q.size() == 2) return 0;
        if (Q.size() == 3) return 0;
        for(int u : Q) for(int v : Q) if (u != v && adj[u][v] != 3) return 0;
        REP(i, 1, Q.size()) ans[Q[i - 1]][Q[i]] = ans[Q[i]][Q[i - 1]] = 1;
        ans[Q[0]][Q.back()] = ans[Q.back()][Q[0]] = 1;
        ans[Q[0]][Q[2]] = ans[Q[2]][Q[0]] = 1;
    }

    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
supertrees.cpp:44:9: note: in expansion of macro 'REP'
   44 |         REP(i, 1, Q.size()) ans[Q[i - 1]][Q[i]] = ans[Q[i]][Q[i - 1]] = 1;
      |         ^~~
supertrees.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
supertrees.cpp:54:9: note: in expansion of macro 'REP'
   54 |         REP(i, 1, Q.size()) ans[Q[i - 1]][Q[i]] = ans[Q[i]][Q[i - 1]] = 1;
      |         ^~~
supertrees.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
supertrees.cpp:65:9: note: in expansion of macro 'REP'
   65 |         REP(i, 1, Q.size()) ans[Q[i - 1]][Q[i]] = ans[Q[i]][Q[i - 1]] = 1;
      |         ^~~

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