oj.uz

Submission #783121

# Submission time Handle Problem Language Result Execution time Memory
783121 2023-07-14T15:43:32 Z teokakabadze Connecting Supertrees (IOI20_supertrees) C++17
65 / 100
 244 ms 27904 KB 
#include "supertrees.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

int a[1005][1005], i, j, f[1005], a2, a3, k, l, cnt, c, pr[1005];
vector<int> s, d, e;

int construct(std::vector<std::vector<int>> p)
{
	int n = p.size();
	std::vector<std::vector<int>> answer;
	for(i = 0; i < n; i++)
    {
        a2 = a3 = 0;
        for(j = 0; j < n; j++)
        {
            if(p[i][j] == 2) a2 = 1;
            if(p[i][j] == 3) a3 = 1;
        }
        if(a2 && a3) return 0;
        //cout << i << "A\n";
		if(!f[i])
        {
            e.clear(); d.clear();
            if(a2) k = 2; else if(a3) k = 3;  else k = 1;
            f[i] = 1, l = i, cnt = 0;
            for(int b = 0; b < n; b++)
            {
                if(i != b && !f[b] && p[i][b] == 1) { f[b] = 1, a[i][b] = a[b][i] = 1; e.pb(b); pr[b] = i; }
                if(f[b] == 2 && p[i][b]) return 0;
            }
            d.pb(i);
            for(j = 0; j < n; j++)
            if(!f[j] && p[l][j] == k)
            {
                f[j] = 1;
                d.pb(j);
                a[l][j] = a[j][l] = 1;
                for(int b = 0; b < n; b++)
                {
                    if(j != b && !f[b] && p[j][b] == 1) { f[b] = 1, a[j][b] = a[b][j] = 1; e.pb(b); pr[b] = j; }
                    if(f[b] == 2 && p[j][b]) return 0;
                }
                l = j;
                cnt++;
                if(cnt == 2) c = j;
            }
            if(k == 2 && cnt < 2) return 0;
            if(k == 2) a[l][i] = a[i][l] = 1;
            if(k == 3 && cnt < 3) return 0;
            if(k == 3) a[l][i] = a[i][l] = a[i][c] = a[c][i] = 1;
            for(j = 0; j < n; j++)
            if(f[j] == 1) f[j] = 2;
            for(auto x : d)
            for(auto y : e)
            if(!a[x][y] && p[x][y] != k) return 0;
            for(auto x : d)
            for(auto y : d)
            if(x != y && p[x][y] != k) return 0;
            for(auto x : e)
            for(auto y : e)
            {
                if(x != y && pr[x] != pr[y] && p[x][y] != k) return 0;
                if(x != y && pr[x] == pr[y] && p[x][y] != 1) return 0;
            }
        }

	}
	for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        s.push_back(a[i][j]);
        answer.push_back(s);
        s.clear();
    }
	build(answer);
	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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 2004 KB Output is correct
7 Correct 162 ms 26392 KB Output is correct

Subtask #2
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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 2004 KB Output is correct
7 Correct 162 ms 26392 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1304 KB Output is correct
13 Correct 167 ms 22408 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 4 ms 1064 KB Output is correct
17 Correct 69 ms 10868 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 41 ms 7956 KB Output is correct
21 Correct 164 ms 27904 KB Output is correct
22 Correct 164 ms 27408 KB Output is correct
23 Correct 163 ms 27852 KB Output is correct
24 Correct 169 ms 24252 KB Output is correct
25 Incorrect 160 ms 27852 KB Answer gives possible 1 while actual possible 0
26 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 9 ms 1236 KB Output is correct
9 Correct 164 ms 22452 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 8 ms 2072 KB Output is correct
13 Correct 170 ms 26308 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 980 KB Output is correct
17 Correct 82 ms 10820 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 42 ms 7840 KB Output is correct
22 Correct 166 ms 26432 KB Output is correct
23 Correct 182 ms 26316 KB Output is correct
24 Correct 171 ms 26340 KB Output is correct
25 Correct 70 ms 8952 KB Output is correct
26 Correct 65 ms 9976 KB Output is correct
27 Correct 162 ms 26236 KB Output is correct
28 Correct 190 ms 26388 KB Output is correct
29 Correct 67 ms 9000 KB Output is correct

Subtask #4
35.0 / 35.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 1 ms 340 KB Output is correct
4 Correct 47 ms 7852 KB Output is correct
5 Correct 164 ms 26328 KB Output is correct
6 Correct 173 ms 25816 KB Output is correct
7 Correct 183 ms 26348 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 43 ms 7816 KB Output is correct
10 Correct 177 ms 26336 KB Output is correct
11 Correct 171 ms 26332 KB Output is correct
12 Correct 176 ms 26320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 48 ms 7896 KB Output is correct
17 Correct 174 ms 26344 KB Output is correct
18 Correct 178 ms 25948 KB Output is correct
19 Correct 244 ms 25892 KB Output is correct
20 Correct 185 ms 22688 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 2004 KB Output is correct
7 Correct 162 ms 26392 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1304 KB Output is correct
13 Correct 167 ms 22408 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 4 ms 1064 KB Output is correct
17 Correct 69 ms 10868 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 41 ms 7956 KB Output is correct
21 Correct 164 ms 27904 KB Output is correct
22 Correct 164 ms 27408 KB Output is correct
23 Correct 163 ms 27852 KB Output is correct
24 Correct 169 ms 24252 KB Output is correct
25 Incorrect 160 ms 27852 KB Answer gives possible 1 while actual possible 0
26 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 2004 KB Output is correct
7 Correct 162 ms 26392 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 7 ms 1304 KB Output is correct
13 Correct 167 ms 22408 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 4 ms 1064 KB Output is correct
17 Correct 69 ms 10868 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 41 ms 7956 KB Output is correct
21 Correct 164 ms 27904 KB Output is correct
22 Correct 164 ms 27408 KB Output is correct
23 Correct 163 ms 27852 KB Output is correct
24 Correct 169 ms 24252 KB Output is correct
25 Incorrect 160 ms 27852 KB Answer gives possible 1 while actual possible 0
26 Halted 0 ms 0 KB -