oj.uz

Submission #927401

# Submission time Handle Problem Language Result Execution time Memory
927401 2024-02-14T20:01:09 Z VMaksimoski008 Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 154 ms 22040 KB 
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
 
struct DSU {
    int n, comp;
    vector<int> par, size;
 
    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }
 
    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }
 
    bool uni(int u, int v) {
        u = get(u), v = get(v);
 
        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);
 
        size[u] += size[v];
        par[v] = u;
        comp--;
 
        return true;
    }
 
    int getComp() { return comp; }
    int getSize(int u) { return size[get(u)]; }
    bool sameSet(int u, int v) { return get(u) == get(v); }
    bool isLeader(int u) { return get(u) == u; }
};

vector<vector<int> > graph;
vector<bool> vis;
vector<int> G;

void dfs(int u) {
    vis[u] = 1;
    G.push_back(u);

    for(int &v : graph[u]) {
        if(vis[v]) continue;
        dfs(v);
    }
}
 
int construct(vector<vector<int> > p) {
    int n = p.size();
    vector<int> cnt(4);
    vector<vector<int> > B(n, vector<int>(n, 0));
    graph.resize(n);
    vis.resize(n);

    DSU dsu; dsu.config(n);

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cnt[p[i][j]]++;

    if(cnt[1] == n && cnt[1] + cnt[0] == n*n) {
        build(B);
        return 1;
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i == j) continue;
            if(p[i][j] == 3) return 0;
            if(dsu.uni(i, j))
                B[i][j] = B[j][i] = 1;
        }
    }

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(i != j && dsu.sameSet(i, j) && p[i][j] == 0) return 0;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i != j && p[i][j] == 2 && dsu.isLeader(i) && dsu.isLeader(j)) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }

    for(int i=0; i<n; i++) {
        if(vis[i]) continue;

        G.clear();
        dfs(i);

        if(G.size() == 2) return 0;
        if(G.size() == 1) continue;

        for(int i=0; i<G.size()-1; i++)
            for(int j=i+1; j<G.size(); j++)
                if(p[i][j] != 2) return 0;

        G.push_back(G[0]);
        for(int i=0; i<G.size()-1; i++)
            B[G[i]][G[i+1]] = B[G[i+1]][G[i]] = 1;
    }

    build(B);
    return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i=0; i<G.size()-1; i++)
      |                      ~^~~~~~~~~~~
supertrees.cpp:105:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for(int j=i+1; j<G.size(); j++)
      |                            ~^~~~~~~~~
supertrees.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int i=0; i<G.size()-1; i++)
      |                      ~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 154 ms 22040 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 154 ms 22040 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 142 ms 22020 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 68 ms 12296 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 16 ms 3420 KB Answer gives possible 0 while actual possible 1
21 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB Output is correct
2 Incorrect 0 ms 344 KB Too few ways to get from 0 to 1, should be 2 found 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 154 ms 22040 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 142 ms 22020 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 68 ms 12296 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 16 ms 3420 KB Answer gives possible 0 while actual possible 1
21 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 154 ms 22040 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 142 ms 22020 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 856 KB Output is correct
17 Correct 68 ms 12296 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 16 ms 3420 KB Answer gives possible 0 while actual possible 1
21 Halted 0 ms 0 KB -