oj.uz

Submission #301512

# Submission time Handle Problem Language Result Execution time Memory
301512 2020-09-18T03:35:40 Z kevinsogo Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 284 ms 26232 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> get_comp(const vector<vector<int>>& adj, vector<bool>& vis, int s) {
    assert(!vis[s]);
    vis[s] = true;
    vector<int> que(1, s);
    for (int f = 0; f < que.size(); f++) {
        int i = que[f];
        assert(vis[i]);
        for (int j : adj[i]) {
            if (!vis[j]) {
                vis[j] = true;
                que.push_back(j);
            }
        }
    }
    return que;
}


int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> ans(n, vector<int>(n));
    vector<vector<int>> adjtree(n), adjcycl(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3) return 0;
            if (p[i][j] == 1) adjtree[i].push_back(j);
        }
    }

    vector<vector<int>> trees;
    vector<int> roots;
    vector<bool> vis(n);
    for (int s = 0; s < n; s++) {
        if (!vis[s]) {
            trees.push_back(get_comp(adjtree, vis, s));
            roots.push_back(trees.back().back());
        }
    }

    for (int t1 = 0; t1 < trees.size(); t1++) {
        for (int t2 = 0; t2 < trees.size(); t2++) {
            if (t1 == t2) continue;
            int target = p[roots[t1]][roots[t2]];
            if (target == 0 && t1 == t2) return 0;
            if (target == 1 && t1 != t2) return 0;
            if (target == 2 && t1 == t2) return 0;
            for (int i1 : trees[t1]) for (int i2 : trees[t2]) {
                if (p[i1][i2] != target) return 0;
            }
        }
    }

    // build trees
    for (auto& tree : trees) {
        for (int i = 1; i < tree.size(); i++) {
            ans[tree[0]][tree[i]] = 1;
        }
    }

    // build cycles
    for (int i : roots) for (int j : roots) {
        if (p[i][j] == 2) adjcycl[i].push_back(j);
    }
    vis = vector<bool>(n);
    for (int s : roots) {
        if (!vis[s]) {
            vector<int> cycle = get_comp(adjcycl, vis, s);
            if (cycle.size() > 1) {
                for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = i++) {
                    ans[cycle[i]][cycle[j]] = 1;
                }
            }
            if (cycle.size() == 2) return 0;
        }
    }


    // fix grid
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[i][j] |= ans[j][i];
            ans[j][i] |= ans[i][j];
        }
    }

    build(ans);
    return 1;
}

Compilation message

supertrees.cpp: In function 'std::vector<int> get_comp(const std::vector<std::vector<int> >&, std::vector<bool>&, int)':
supertrees.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int f = 0; f < que.size(); f++) {
      |                     ~~^~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:44:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int t1 = 0; t1 < trees.size(); t1++) {
      |                      ~~~^~~~~~~~~~~~~~
supertrees.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int t2 = 0; t2 < trees.size(); t2++) {
      |                          ~~~^~~~~~~~~~~~~~
supertrees.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i = 1; i < tree.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:73:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = i++) {
      |                                                       ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1408 KB Output is correct
7 Correct 277 ms 26232 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1408 KB Output is correct
7 Correct 277 ms 26232 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 262 ms 22488 KB Output is correct
14 Incorrect 1 ms 256 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 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 11 ms 1280 KB Output is correct
9 Correct 252 ms 22264 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 12 ms 1408 KB Output is correct
13 Correct 284 ms 26232 KB Output is correct
14 Incorrect 1 ms 256 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 63 ms 5880 KB Output is correct
5 Correct 273 ms 22648 KB Output is correct
6 Correct 256 ms 22264 KB Output is correct
7 Correct 264 ms 24184 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 67 ms 5880 KB Output is correct
10 Correct 261 ms 22904 KB Output is correct
11 Correct 261 ms 22264 KB Output is correct
12 Correct 272 ms 25336 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 66 ms 6008 KB Output is correct
17 Correct 261 ms 22776 KB Output is correct
18 Correct 267 ms 22520 KB Output is correct
19 Correct 263 ms 22396 KB Output is correct
20 Correct 254 ms 22264 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1408 KB Output is correct
7 Correct 277 ms 26232 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 262 ms 22488 KB Output is correct
14 Incorrect 1 ms 256 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 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1408 KB Output is correct
7 Correct 277 ms 26232 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 11 ms 1280 KB Output is correct
13 Correct 262 ms 22488 KB Output is correct
14 Incorrect 1 ms 256 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -