oj.uz

Submission #372444

# Submission time Handle Problem Language Result Execution time Memory
372444 2021-02-28T08:07:39 Z Lam_lai_cuoc_doi Airline Route Map (JOI18_airline) C++17
0 / 100
 580 ms 15448 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define bit(i, x) (((x) >> (i)) & 1)
void Alice(int n, int m, int a[], int b[])
{
    vector<pair<int, int>> s;
    for (int i = 0; i < m; ++i)
        s.emplace_back(a[i], b[i]);
    for (int j = 0; j < 10; ++j)
    {
        for (int i = 0; i < n; ++i)
            if (bit(j, i))
                s.emplace_back(n + j, i);
        if (j + 1 < 10)
            s.emplace_back(j, j + 1);
    }
    for (int i = 0; i < n; ++i)
        s.emplace_back(n + 10, i);
    for (int i = 0; i < n + 10; ++i)
        s.emplace_back(n + 11, i);
    InitG(n + 12, s.size());
    int pos(0);
    for (auto i : s)
        MakeG(pos++, i.first, i.second);
}
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define bit(i, x) (((x) >> (i)) & 1)
void Bob(int n, int m, int a[], int b[])
{
    int ten(-1), elv(-1), nin(-1), zer(-1);
    vector<vector<bool>> adj(n, vector<bool>(n));
    vector<pair<int, int>> s;
    vector<int> cnt(n), real(n), son(n), obit, dep(n), pos(10), tmp;
    for (int i = 0; i < m; ++i)
    {
        adj[a[i]][b[i]] = 1;
        ++cnt[a[i]];
        adj[b[i]][a[i]] = 1;
        ++cnt[b[i]];
    }
    /// Find elevent and ten
    for (int i = 0; i < n; ++i)
        if (cnt[i] == n - 1)
        {
            for (int j = 0; j < n; ++j)
                if (i != j && !adj[i][j] && cnt[j] == n - 12)
                {
                    ten = j;
                    elv = i;
                    break;
                }
            if (ten != -1)
                break;
        }
    /// find bit
    auto bfs = [&](int v) {
        fill(dep.begin(), dep.end(), 0);
        dep[v] = 1;
        queue<int> q;
        q.emplace(v);
        while (q.size())
        {
            int c = q.front();
            q.pop();
            pos[dep[c] - 1] = c;
            for (auto i : obit)
                if (!dep[i] && adj[c][i])
                {
                    ++son[c];
                    dep[i] = dep[v] + 1;
                }
        }
    };
    for (int i = 0; i < n; ++i)
        if (i != elv && !adj[ten][i])
            obit.emplace_back(i);
    bfs(obit[0]);
    for (auto i : obit)
        if (son[i] == 0)
            tmp.emplace_back(i);
    if (tmp.size() == 1)
        bfs(cnt[tmp.back()] > cnt[obit[0]] ? tmp.back() : obit[0]);
    else
        bfs(cnt[tmp[0]] > cnt[tmp[1]] ? tmp[0] : tmp[1]);
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < n; ++j)
            if (adj[pos[i]][j])
                real[j] |= 1 << i;
    for (int i = 0; i < n; ++i)
        if (adj[ten][i])
            for (int j = i + 1; j < n; ++j)
                if (adj[ten][j])
                    s.emplace_back(real[i], real[j]);
    InitMap(n - 12, s.size());
    for (auto i : s)
        MakeMap(i.first, i.second);
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:7:27: warning: unused variable 'nin' [-Wunused-variable]
    7 |     int ten(-1), elv(-1), nin(-1), zer(-1);
      |                           ^~~
Bob.cpp:7:36: warning: unused variable 'zer' [-Wunused-variable]
    7 |     int ten(-1), elv(-1), nin(-1), zer(-1);
      |                                    ^~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3436 KB Wrong Answer [9]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3436 KB Wrong Answer [9]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 580 ms 15448 KB Wrong Answer [9]
2 Halted 0 ms 0 KB -