Submission #628346

# Submission time Handle Problem Language Result Execution time Memory
628346 2022-08-13T10:43:24 Z boris_mihov Connecting Supertrees (IOI20_supertrees) C++17
21 / 100
248 ms 30152 KB
#include "supertrees.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXN = 1000 + 10;

int n;
int p[MAXN];
int d[MAXN];
std::vector < std::vector <int> > ans;
std::vector <int> byPaths[MAXN][3];

inline int find(int x)
{
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}

inline void connect(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (d[x] > d[y]) std::swap(x, y);
    if (d[x] == d[y]) ++d[y];
    p[x] = y;
}

inline bool areConnected(int x, int y)
{
    return find(x) == find(y);
}

int cycle[MAXN], cycleCnt;
int construct(std::vector < std::vector <int> > wantedPaths) 
{
    n = wantedPaths.size();
    ans.resize(n);

    for (int i = 1 ; i <= n ; ++i)
    {
        ans[i-1].resize(n, 0);
        for (int j = 1 ; j <= n ; ++j)
        {
            if (i == j) continue;
            if (wantedPaths[i - 1][j - 1] == 3) return 0;
            byPaths[i][wantedPaths[i - 1][j - 1]].push_back(j);
        }
    }

    std::iota(p + 1, p + 1 + n, 1);
    std::fill(d + 1, d + 1 + n, 1);
    for (int i = 1 ; i <= n ; ++i)
    {
        int last = i;
        int alreadyConnected = 0;
        for (const int &j : byPaths[i][2])
        {
            if (areConnected(i, j)) 
            {
                if (alreadyConnected == 1) return 0;
                cycle[i] = cycle[j];
                alreadyConnected = 2;
                continue;
            }

            if (alreadyConnected == 2 || cycle[j] != 0) return 0;
            if (cycle[i] == 0) cycle[i] = ++cycleCnt;
            ans[last - 1][j - 1] = 1;
            ans[j - 1][last - 1] = 1;
            alreadyConnected = 1;
            cycle[j] = cycle[i];
            connect(i, j);
            last = j;
        }

        if (last != i)
        {
            ans[last - 1][i - 1] = 1;
            ans[i - 1][last - 1] = 1;
        }

        for (const int &j : byPaths[i][1])
        {
            if (areConnected(i, j)) continue;
            ans[i - 1][j - 1] = 1;
            ans[j - 1][i - 1] = 1;
            connect(i, j);
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            if (i == j) continue;
            if (cycle[i] != cycle[j] && cycle[i] != 0 && cycle[j] != 0 && areConnected(i, j)) return 0;
            if (wantedPaths[i - 1][j - 1] == 0 && areConnected(i, j)) return 0;
            if (wantedPaths[i - 1][j - 1] == 1 && ((cycle[i] != 0 && cycle[j] != 0 && cycle[i] == cycle[j]) || !areConnected(i, j))) return 0;
            if (wantedPaths[i - 1][j - 1] == 2 && (!areConnected(i, j) || (cycle[i] != cycle[j] && cycle[i] != 0 && cycle[j] != 0))) return 0;
        }
    }

    build(ans);
	return 1;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 201 ms 28112 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 201 ms 28112 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 8 ms 1520 KB Output is correct
13 Correct 194 ms 28228 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 124 ms 19016 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 49 ms 7392 KB Output is correct
21 Correct 221 ms 28752 KB Output is correct
22 Correct 202 ms 28096 KB Output is correct
23 Correct 237 ms 28132 KB Output is correct
24 Correct 221 ms 28112 KB Output is correct
25 Correct 83 ms 18756 KB Output is correct
26 Correct 98 ms 18112 KB Output is correct
27 Correct 223 ms 30024 KB Output is correct
28 Correct 199 ms 28100 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 51 ms 7360 KB Output is correct
5 Correct 248 ms 28672 KB Output is correct
6 Correct 214 ms 28112 KB Output is correct
7 Correct 222 ms 28108 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 50 ms 7324 KB Output is correct
10 Correct 200 ms 28744 KB Output is correct
11 Correct 209 ms 28104 KB Output is correct
12 Correct 220 ms 30152 KB Output is correct
13 Correct 1 ms 376 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Answer gives possible 0 while actual possible 1
16 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 201 ms 28112 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 8 ms 1520 KB Output is correct
13 Correct 194 ms 28228 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 124 ms 19016 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 49 ms 7392 KB Output is correct
21 Correct 221 ms 28752 KB Output is correct
22 Correct 202 ms 28096 KB Output is correct
23 Correct 237 ms 28132 KB Output is correct
24 Correct 221 ms 28112 KB Output is correct
25 Correct 83 ms 18756 KB Output is correct
26 Correct 98 ms 18112 KB Output is correct
27 Correct 223 ms 30024 KB Output is correct
28 Correct 199 ms 28100 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Incorrect 1 ms 340 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 201 ms 28112 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 8 ms 1520 KB Output is correct
13 Correct 194 ms 28228 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 1108 KB Output is correct
17 Correct 124 ms 19016 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 49 ms 7392 KB Output is correct
21 Correct 221 ms 28752 KB Output is correct
22 Correct 202 ms 28096 KB Output is correct
23 Correct 237 ms 28132 KB Output is correct
24 Correct 221 ms 28112 KB Output is correct
25 Correct 83 ms 18756 KB Output is correct
26 Correct 98 ms 18112 KB Output is correct
27 Correct 223 ms 30024 KB Output is correct
28 Correct 199 ms 28100 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Incorrect 1 ms 340 KB Answer gives possible 1 while actual possible 0
33 Halted 0 ms 0 KB -