oj.uz

Submission #300239

# Submission time Handle Problem Language Result Execution time Memory
300239 2020-09-17T02:08:21 Z mth1908 Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define ll long long
#define ull unsigned long long
#define ar array
#define pii pair<int, int>
#define sz(s) (int) s.size()
#define all(s) s.begin(), s.end()

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int construct (vector<vector<int>> p) {
    int n = sz(p);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3) return 0;
        }
    }
    vector<vector<int>> b(n, vector<int>(n, 0));
    vector<bool> vis(n, 0);
    vector<int> comp(n), line(n);
    for (int v = 0; v < n; v++) {
        if (vis[v]) continue;
        queue<int> q;
        q.push(v);
        vector<int> cyc;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            if (vis[x]) continue;
            vector<int> cur_l;
            queue<int> q_l;
            q_l.push(x);
            cyc.push_back(x);
            while (!q_l.empty()) {
                int y = q_l.front(); q.pop();
                if (vis[y]) continue;
                cur_l.push_back(y);
                vis[y] = true;
                comp[y] = v;
                line[y] = x;
                for (int i = 0; i < n; i++) {
                    if (p[y][i] == 2) q.push(i);
                    else if (p[y][i] == 1) q_l.push(i);
                }
            }
            if (sz(cur_l) > 1) {
                for (int i = 0; i < sz(cur_l) - 1; i++) {
                    int m = cur_l[i], n = cur_l[i + 1];
                    b[m][n] = b[n][m] = 1;
                }
            }
        }
        if (sz(cyc) == 2) return 0;
        if (sz(cyc) == 1) continue;
        for (int i = 0; i < sz(cyc); i++) {
            int m = cyc[i];
            int n = cyc[(i + 1) % sz(cyc)];
            b[m][n] = b[n][m] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (line[i] == line[j]) {
                if (p[i][j] != 1) return 0;
            }
            else if (comp[i] == comp[j]) {
                if (p[i][j] != 2) return 0;
            }
            else {
                if (p[i][j] != 0) return 0;
            }
        }
    }
    build(b);
    return 1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -