oj.uz

Submission #593599

# Submission time Handle Problem Language Result Execution time Memory
593599 2022-07-11T12:26:16 Z kenjinemera Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 234 ms 24096 KB 
#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

/* 
    Sub 1 + 2: Construct numerous connected components
    Sub 3: Add cycle to the numerous components (break if component size == 2)
    Sub 4: Build many trees and loop around their roots
    Sub 5: Verify that Law Of Tree works
    Sub 6: We can't allow 3 since we would need 4
*/

typedef long long int64;
#define pb push_back
#define f first
#define s second
#define vi vector<int>

const int MAXN = 1010;
bool vis[MAXN];

int construct(vector<vector<int>> p)
{
	int n = p.size();
	vector<vi> answer;

	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

    for (int i = 0; i < n - 1; i++)
    {
          if (vis[i]) continue;
          int cycle_count = 1;
          int prev_link = i;
    
          // how are we going to verify the law of the tree?
    
          for (int j =  i + 1; j < n; j++)
          {
              if (p[i][j] == 3) return 0;
              if (p[i][j] == 0) continue;
    
              vis[j] = 1;
    
              if (p[i][j] == 2)
              {
                  answer[prev_link][j] = 1;
                  answer[j][prev_link] = 1;
                  prev_link = j;
                  cycle_count++;

                  for (int k = j + 1; k < n; k++)
                  {
                        if (p[j][k] == 1) {
                            answer[j][k] = 1;
                            answer[k][j] = 1;
                            vis[k] = 1;
                        }
                  }

              } else if (p[i][j] == 1)
              {
                  answer[i][j] = 1;
                  answer[j][i] = 1;
                  vis[j] = 1;
              }                          
          }
    
          if (cycle_count == 2) return 0;
          else if (cycle_count > 2) {
              answer[i][prev_link] = 1;
              answer[prev_link][i] = 1;
          }
    }

    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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 14 ms 1236 KB Output is correct
7 Correct 172 ms 23960 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 14 ms 1236 KB Output is correct
7 Correct 172 ms 23960 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 10 ms 1332 KB Output is correct
13 Correct 234 ms 23948 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 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 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 8 ms 1236 KB Output is correct
9 Correct 225 ms 23972 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 11 ms 1204 KB Output is correct
13 Correct 196 ms 23932 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
16 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 52 ms 6152 KB Output is correct
5 Correct 187 ms 23920 KB Output is correct
6 Correct 180 ms 23904 KB Output is correct
7 Correct 187 ms 23920 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 47 ms 6220 KB Output is correct
10 Correct 181 ms 23920 KB Output is correct
11 Correct 226 ms 23924 KB Output is correct
12 Correct 232 ms 24096 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 48 ms 6220 KB Too many ways to get from 0 to 352, should be 2 found no less than 3
17 Halted 0 ms 0 KB -

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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 14 ms 1236 KB Output is correct
7 Correct 172 ms 23960 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 10 ms 1332 KB Output is correct
13 Correct 234 ms 23948 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 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 14 ms 1236 KB Output is correct
7 Correct 172 ms 23960 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 10 ms 1332 KB Output is correct
13 Correct 234 ms 23948 KB Output is correct
14 Incorrect 1 ms 212 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -