oj.uz

Submission #301507

# Submission time Handle Problem Language Result Execution time Memory
301507 2020-09-18T03:31:43 Z kevinsogo Connecting Supertrees (IOI20_supertrees) C++17
46 / 100
 267 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;
                }
            }
        }
    }


    // 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 128 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 12 ms 1408 KB Output is correct
7 Correct 266 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 128 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 12 ms 1408 KB Output is correct
7 Correct 266 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 261 ms 22264 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 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 0 ms 256 KB Answer gives possible 1 while actual possible 0
5 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 64 ms 5880 KB Output is correct
5 Correct 255 ms 22648 KB Output is correct
6 Correct 250 ms 22264 KB Output is correct
7 Correct 262 ms 24312 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 68 ms 5880 KB Output is correct
10 Correct 257 ms 22776 KB Output is correct
11 Correct 255 ms 22264 KB Output is correct
12 Correct 267 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 64 ms 5880 KB Output is correct
17 Correct 262 ms 22776 KB Output is correct
18 Correct 255 ms 22520 KB Output is correct
19 Correct 259 ms 22392 KB Output is correct
20 Correct 257 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 128 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 12 ms 1408 KB Output is correct
7 Correct 266 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 261 ms 22264 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 128 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 12 ms 1408 KB Output is correct
7 Correct 266 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 261 ms 22264 KB Output is correct
14 Incorrect 1 ms 256 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -