oj.uz

Submission #566018

# Submission time Handle Problem Language Result Execution time Memory
566018 2022-05-21T16:44:11 Z Spade1 Airline Route Map (JOI18_airline) C++14
0 / 100
 494 ms 16620 KB 
#include<bits/stdc++.h>
#include "Alicelib.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

int cnt = 0;

void Alice(int N, int M, int A[], int B[]) {
    int binarycount = 0;
    for (int i = 1; i <= N; ++i) {
        binarycount += __builtin_popcount(i);
    }
    InitG(N+12, N+M+binarycount+10);
    for (int i = 0; i < M; ++i) {
        MakeG(cnt++, A[i], B[i]);
    }
    for (int i = 0; i < N; ++i) {
        MakeG(cnt++, N, i);
    }
    MakeG(cnt++, N+1, N);
    for (int i = N+2; i < N+11; ++i) {
        MakeG(cnt++, i, i+1);
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (i & (1<<j)) MakeG(cnt++, i-1, N+2+j);
        }
    }
}

#include<bits/stdc++.h>
#include "Boblib.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

vector<int> adj[1050];
int unmap[1050];
int bit[11];
bool part[1050];
int deg[1050];
set<int> sbit;

void findbit(int i) {
    if (i == 9) return;
    for (auto j : adj[bit[i]]) {
        if (!sbit.count(j) && !part[j]) {
            bit[i+1] = j;
            sbit.insert(j);
            findbit(i+1);
            break;
        }
    }
}

void Bob(int V, int U, int C[], int D[]) {
    int binarycount = 0;
    for (int i = 0; i < V; ++i) unmap[i] = -1;
    for (int i = 1; i <= (V-12); ++i) {
        binarycount += __builtin_popcount(i);
    }
    int N = V-12, M = U-V+2-binarycount;
    InitMap(N, M);
    for (int i = 0; i < V; ++i) {
        adj[C[i]].pb(D[i]);
        adj[D[i]].pb(C[i]);
        deg[C[i]]++, deg[D[i]]++;
    }
    int c = 0;
    int key = -1, ckey = -1;
    for (int i = 0; i < V; ++i) {
        if (deg[i] == 1 && deg[adj[i][0]] == N+1) {
            key = adj[i][0];
            ckey = i;
            c++;
        }
    }
    if (c > 1) exit(0);

    for (auto i : adj[key]) {
        if (i != ckey) part[i] = 1;
    }

    vector<int> edge;
    for (int i = 0; i < V; ++i) {
        if (i == key || i == ckey) continue;
        if (!part[i]) {
            int cnt = 0;
            for (auto j : adj[i]) {
                if (!part[j]) cnt++;
            }
            if (cnt == 1) edge.pb(i);
        }
    }

    if (deg[edge[0]] > deg[edge[1]]) bit[0] = edge[0];
    else bit[0] = edge[1];

    sbit.insert(bit[0]);
    findbit(0);

    for (int i = 0; i < V; ++i) {
        if (i == key || i == ckey) continue;
        if (sbit.count(i)) continue;
        for (auto k : adj[i]) {
            for (int j = 0; j < 10; ++j) {
                if (k == bit[j]) unmap[i] += (1<<j);
            }
        }
    }

    for (int i = 0; i < U; ++i) {
        if (unmap[C[i]] == -1) continue;
        if (unmap[D[i]] == -1) continue;
        MakeMap(unmap[D[i]], unmap[C[i]]);
    }
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4608 KB Wrong Answer [17]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4608 KB Wrong Answer [17]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 16620 KB Wrong Answer [12]
2 Halted 0 ms 0 KB -