oj.uz

Submission #800078

# Submission time Handle Problem Language Result Execution time Memory
800078 2023-08-01T09:48:59 Z becaido Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 198 ms 24004 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "supertrees.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
void build(vector<vector<int>> b);
#endif

const int SIZE = 1005;

int n, mx;
bool vs[SIZE];
vector<vector<int>> ans;

int construct(vector<vector<int>> p) {
	n = p.size();
	ans.resize(n, vector<int>(n));
	FOR (i, 0, n - 1) mx = max(mx, *max_element(p[i].begin(), p[i].end()));
	if (mx == 0) {
        build(ans);
        return 1;
	}
	if (mx == 1) {
        fill(vs, vs + n, 0);
        FOR (i, 0, n - 1) if (!vs[i]) {
            vector<int> all;
            queue<int> q;
            vs[i] = 1, q.push(i);
            while (q.size()) {
                int pos = q.front();
                q.pop();
                all.pb(pos);
                FOR (j, 0, n - 1) if (p[i][j] && !vs[j]) {
                    q.push(j);
                    vs[j] = 1;
                }
            }
            for (int x : all) for (int y : all) if (!p[x][y]) return 0;
            FOR (j, 1, all.size() - 1) ans[all[j]][all[j - 1]] = ans[all[j - 1]][all[j]] = 1;
        }
        build(ans);
        return 1;
	}
	fill(vs, vs + n, 0);
    FOR (i, 0, n - 1) if (!vs[i]) {
        vector<int> all;
        queue<int> q;
        vs[i] = 1, q.push(i);
        while (q.size()) {
            int pos = q.front();
            q.pop();
            all.pb(pos);
            FOR (j, 0, n - 1) if (p[i][j] && !vs[j]) {
                q.push(j);
                vs[j] = 1;
            }
        }
        if (all.size() == 1) continue;
        if (all.size() == 2) return 0;
        for (int x : all) for (int y : all) if (!p[x][y]) return 0;
        FOR (j, 1, all.size() - 1) ans[all[j]][all[j - 1]] = ans[all[j - 1]][all[j]] = 1;
        ans[all[0]][all.back()] = ans[all.back()][all[0]] = 1;
    }
    build(ans);
    return 1;
}

/*
in1
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
out1
1
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

in2
2
1 0
0 1
out2
1
0 0
0 0

in3
2
1 3
3 1
out3
0
*/

#ifdef WAIMAI
static int nn;
static vector<vector<int>> pp;
static vector<vector<int>> bb;
static bool called = false;

static void check(bool cond, string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}

void build(vector<vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == nn, "Invalid number of rows in b");
    for (int i = 0; i < nn; i++) {
        check((int)_b[i].size() == nn, "Invalid number of columns in b");
    }
    bb = _b;
}

int main() {
    assert(scanf("%d", &nn) == 1);

    pp.resize(nn);
    for (int i = 0; i < nn; i++) {
        pp[i].resize(nn);
    }

    for (int i = 0; i < nn; i++) {
        for (int j = 0; j < nn; j++) {
            assert(scanf("%d", &pp[i][j]) == 1);
        }
    }
    fclose(stdin);

    int possible = construct(pp);

    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 < nn; i++) {
            for (int j = 0; j < nn; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", bb[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}
#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 10 ms 1180 KB Output is correct
7 Correct 173 ms 22712 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 10 ms 1180 KB Output is correct
7 Correct 173 ms 22712 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1208 KB Output is correct
13 Correct 153 ms 23160 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 155 ms 23424 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1212 KB Output is correct
13 Correct 161 ms 23896 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 38 ms 6244 KB Output is correct
5 Correct 194 ms 23988 KB Output is correct
6 Correct 198 ms 23896 KB Output is correct
7 Correct 183 ms 23984 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 38 ms 6196 KB Output is correct
10 Correct 153 ms 23972 KB Output is correct
11 Correct 156 ms 23984 KB Output is correct
12 Correct 170 ms 24004 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 1 ms 212 KB Too many ways to get from 4 to 8, should be 1 found no less than 2
15 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 10 ms 1180 KB Output is correct
7 Correct 173 ms 22712 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1208 KB Output is correct
13 Correct 153 ms 23160 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 10 ms 1180 KB Output is correct
7 Correct 173 ms 22712 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 216 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1208 KB Output is correct
13 Correct 153 ms 23160 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -