oj.uz

Submission #422123

# Submission time Handle Problem Language Result Execution time Memory
422123 2021-06-09T18:14:00 Z Mohammed_Alsaad Connecting Supertrees (IOI20_supertrees) C++17
11 / 100
 236 ms 24072 KB 
#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B> string to_string(pair<A, B> p);
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);

string to_string(const string &s)
{
    return '"' + s + '"';
}
string to_string(const char *s)
{
    return to_string((string)s);
}
string to_string(bool b)
{
    return (b ? "true" : "false");
}

template <size_t N> string to_string(bitset<N> v)
{
    string res = "";
    for (size_t i = 0; i < N; i++)
    {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}
template <typename A> string to_string(A v)
{
    bool first = true;
    string res = "{";
    for (const auto &x : v)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B> string to_string(pair<A, B> p)
{
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " +
           to_string(get<3>(p)) + ")";
}
void dbg_out()
{
    cout << endl;
}
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T)
{
    cout << " " << to_string(H);
    dbg_out(T...);
}

#define FAST_IO                                                                                                        \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(NULL);                                                                                                     \
    cout.tie(NULL);

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", dbg_out(__VA_ARGS__)
#define edl() cout << endl;

#define rep(i, a, b) for (int i = a; i < b; i++)

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define pf push_front
#define mp make_pair

#define F first
#define S second

#define min_self(x, y) x = min(x, y)
#define max_self(x, y) x = max(x, y)

typedef long long ll;
ll const INF = 2147483647, R_INF = 9223372036854775807, MOD = 1e9 + 7;

const int mxN = 1e3 + 5;

void build(vector<vector<int>> b);

int cmp;
bool vis[mxN];
vector<vector<int>> component(mxN);

void dfs(int cur, int par, vector<vector<int>> &p)
{
    component[cmp].pb(cur);
    vis[cur] = true;
    rep(u, 0, p.size())
    {
        if (!vis[u] && u != cur && u != par && p[cur][u] == 1)
            dfs(u, cur, p);
    }
}

int construct(vector<vector<int>> p)
{
    int n = p.size();
    vector<vector<int>> res(n, vector<int>(n));
    rep(i, 0, n)
    {
        if (!vis[i])
        {
            dfs(i, i, p);

            rep(j, 1, component[cmp].size()) res[component[cmp][j]][component[cmp][j - 1]] =
                res[component[cmp][j - 1]][component[cmp][j]] = 1;

            cmp++;
        }
    }

    // dbg(res);

    for (int i = cmp - 1; i > 1; i--)
    {
        int one = component[0][0], two = component[i][0];
        if (p[one][two])
        {
            res[one][two] = res[two][one] = 1;
            break;
        }
    }

    // dbg(res);

    rep(i, 1, cmp)
    {
        int one = component[i][0], two = res[i - 1][0];

        if (p[one][two])
            res[one][two] = res[two][one] = 1;
    }
    build(res);
    return 1;
}

/*



*/

Compilation message

supertrees.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&)':
supertrees.cpp:77:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 | #define rep(i, a, b) for (int i = a; i < b; i++)
......
  106 |     rep(u, 0, p.size())
      |         ~~~~~~~~~~~~~~                  
supertrees.cpp:106:5: note: in expansion of macro 'rep'
  106 |     rep(u, 0, p.size())
      |     ^~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:77:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 | #define rep(i, a, b) for (int i = a; i < b; i++)
......
  123 |             rep(j, 1, component[cmp].size()) res[component[cmp][j]][component[cmp][j - 1]] =
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:123:13: note: in expansion of macro 'rep'
  123 |             rep(j, 1, component[cmp].size()) res[component[cmp][j]][component[cmp][j - 1]] =
      |             ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 10 ms 1252 KB Output is correct
7 Correct 236 ms 24072 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 10 ms 1252 KB Output is correct
7 Correct 236 ms 24072 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 10 ms 1228 KB Output is correct
13 Correct 229 ms 23968 KB Output is correct
14 Incorrect 1 ms 204 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 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 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 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 62 ms 6268 KB Output is correct
5 Correct 232 ms 24004 KB Output is correct
6 Correct 233 ms 24016 KB Output is correct
7 Correct 233 ms 24016 KB Output is correct
8 Incorrect 1 ms 204 KB Too few ways to get from 0 to 1, should be 2 found 1
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 10 ms 1252 KB Output is correct
7 Correct 236 ms 24072 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 10 ms 1228 KB Output is correct
13 Correct 229 ms 23968 KB Output is correct
14 Incorrect 1 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 10 ms 1252 KB Output is correct
7 Correct 236 ms 24072 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 10 ms 1228 KB Output is correct
13 Correct 229 ms 23968 KB Output is correct
14 Incorrect 1 ms 204 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -