Submission #835957

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
835957	2023-08-24T00:53:54 Z	maomao90	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	170 ms	27936 KB

supertrees

// I can do all things through Christ who strengthens me
// Philippians 4:13

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 1005;

int n;
vector<vi> g;
vector<vi> ans;
bool vis[MAXN];

bool inc[MAXN];
bool solve(vi comp) {
    if (SZ(comp) == 1) {
        return 1;
    }
    vi cyc, line;
    for (int i : comp) {
        bool all2 = 1;
        for (int j : comp) {
            if (i == j) {
                continue;
            }
            if (g[i][j] != 2) {
                all2 = 0;
                break;
            }
        }
        if (all2) {
            cyc.pb(i);
        } else {
            line.pb(i);
        }
    }
    for (int i : line) {
        if (inc[i]) {
            continue;
        }
        vi chain;
        for (int j : line) {
            if (g[i][j] == 1) {
                chain.pb(j);
            }
        }
        for (int j : chain) {
            inc[j] = 1;
            for (int k : line) {
                if (g[i][k] != g[j][k]) {
                    return 0;
                }
            }
        }
        REP (j, 0, SZ(chain) - 1) {
            ans[chain[j]][chain[j + 1]] = 1;
            ans[chain[j + 1]][chain[j]] = 1;
        }
        cyc.pb(chain[0]);
        if (SZ(chain) == SZ(comp)) {
            return 1;
        }
    }
    if (SZ(cyc) <= 2) {
        assert(0);
        return 0;
    }
    REP (i, 0, SZ(cyc)) {
        ans[cyc[i]][cyc[(i + 1) % SZ(cyc)]] = 1;
        ans[cyc[(i + 1) % SZ(cyc)]][cyc[i]] = 1;
    }
    return 1;
    /*
    if (SZ(cyc) == 1) {
        return 0;
    }
    REP (i, 0, SZ(line) - 1) {
        ans[line[i]][line[i + 1]] = 1;
        ans[line[i + 1]][line[i]] = 1;
    }
    if (!cyc.empty()) {
        REP (i, 0, SZ(cyc) - 1) {
            ans[cyc[i]][cyc[i + 1]] = 1;
            ans[cyc[i + 1]][cyc[i]] = 1;
        }
        ans[line[0]][cyc[0]] = 1;
        ans[cyc[0]][line[0]] = 1;
        ans[line[0]][cyc.back()] = 1;
        ans[cyc.back()][line[0]] = 1;
    }
    */
    return 1;
}

int construct(vector<vi> p) {
    n = SZ(p);
    ans = vector<vi>(n, vi(n, 0));
    g = p;
    REP (i, 0, n) {
        REP (j, 0, n) {
            if (g[i][j] == 3) {
                return 0;
            }
        }
    }
    REP (i, 0, n) {
        if (vis[i]) {
            continue;
        }
        vi comp;
        REP (j, 0, n) {
            if (g[i][j]) {
                comp.pb(j);
            }
        }
        for (int j : comp) {
            vis[j] = 1;
            REP (k, 0, n) {
                if ((g[j][k] > 0) != (g[i][k] > 0)) {
                    return 0;
                }
            }
        }
        if (!solve(comp)) {
            return 0;
        }
    }
    build(ans);
    return 1;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1364 KB	Output is correct
7	Correct	163 ms	25936 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1364 KB	Output is correct
7	Correct	163 ms	25936 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1360 KB	Output is correct
13	Correct	159 ms	25940 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	73 ms	16008 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	44 ms	6732 KB	Output is correct
21	Correct	152 ms	25928 KB	Output is correct
22	Correct	155 ms	25932 KB	Output is correct
23	Correct	168 ms	25932 KB	Output is correct
24	Correct	152 ms	25972 KB	Output is correct
25	Correct	63 ms	16008 KB	Output is correct
26	Correct	59 ms	16008 KB	Output is correct
27	Correct	164 ms	25888 KB	Output is correct
28	Correct	170 ms	26080 KB	Output is correct

Subtask #3
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	Runtime error	1 ms	592 KB	Execution killed with signal 6
5	Halted	0 ms	0 KB	-

Subtask #4
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	38 ms	6740 KB	Output is correct
5	Correct	153 ms	25976 KB	Output is correct
6	Correct	158 ms	25932 KB	Output is correct
7	Correct	164 ms	25940 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	38 ms	6728 KB	Output is correct
10	Correct	156 ms	25992 KB	Output is correct
11	Correct	151 ms	25932 KB	Output is correct
12	Correct	165 ms	25996 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	38 ms	6740 KB	Output is correct
17	Correct	153 ms	27900 KB	Output is correct
18	Correct	155 ms	27936 KB	Output is correct
19	Correct	152 ms	27852 KB	Output is correct
20	Correct	151 ms	27856 KB	Output is correct

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1364 KB	Output is correct
7	Correct	163 ms	25936 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1360 KB	Output is correct
13	Correct	159 ms	25940 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	73 ms	16008 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	44 ms	6732 KB	Output is correct
21	Correct	152 ms	25928 KB	Output is correct
22	Correct	155 ms	25932 KB	Output is correct
23	Correct	168 ms	25932 KB	Output is correct
24	Correct	152 ms	25972 KB	Output is correct
25	Correct	63 ms	16008 KB	Output is correct
26	Correct	59 ms	16008 KB	Output is correct
27	Correct	164 ms	25888 KB	Output is correct
28	Correct	170 ms	26080 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Runtime error	1 ms	592 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	7 ms	1364 KB	Output is correct
7	Correct	163 ms	25936 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	8 ms	1360 KB	Output is correct
13	Correct	159 ms	25940 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	3 ms	852 KB	Output is correct
17	Correct	73 ms	16008 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	44 ms	6732 KB	Output is correct
21	Correct	152 ms	25928 KB	Output is correct
22	Correct	155 ms	25932 KB	Output is correct
23	Correct	168 ms	25932 KB	Output is correct
24	Correct	152 ms	25972 KB	Output is correct
25	Correct	63 ms	16008 KB	Output is correct
26	Correct	59 ms	16008 KB	Output is correct
27	Correct	164 ms	25888 KB	Output is correct
28	Correct	170 ms	26080 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	0 ms	212 KB	Output is correct
32	Runtime error	1 ms	592 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Submission #835957

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 35.0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
35.0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0