oj.uz

Submission #242807

# Submission time Handle Problem Language Result Execution time Memory
242807 2020-06-29T10:39:58 Z osaaateiasavtnl Airline Route Map (JOI18_airline) C++14
0 / 100
 514 ms 11624 KB 
#include<bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
void Alice( int N, int M, int A[], int B[] ){   
    vector <ii> ans;
    for (int i = 0; i < M; ++i)
        ans.app(mp(A[i], B[i]));
 
    // N ... N + 9 - bits
    for (int i = N; i < N + 9; ++i)
        ans.app(mp(i, i + 1));
        
    //N + 10 - connected with all except N + 11, N + 11 - only to bits
    for (int i = 0; i < N + 10; ++i) 
        if (i != N)
            ans.app(mp(i, N + 10));
    for (int i = N; i < N + 10; ++i)
        ans.app(mp(i, N + 11));
 
    for (int u = 0; u < N; ++u)
        for (int bit = 0; bit < 10; ++bit)
            if ((u >> bit) & 1)
                ans.app(mp(u, N+bit));
  
    vector <int> pw(N+12);
    for (auto e : ans) {
        ++pw[e.f];
        ++pw[e.s];
    }   

    for (int i = 0; i < N + 12; ++i) {
        if (i != N + 10 && pw[i] >= pw[N+10]) {
            exit(1);
        }   
    }

    InitG(N + 12, ans.size());
    int ptr = 0;
    for (auto e : ans) {
        MakeG(ptr++, e.f, e.s);
    }
}
 
#include<bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 2007;
bool g[N][N];
 
void Bob( int V, int E, int C[], int D[] ){
    int n = V - 12;

    /*
    if (n == 1) {
        InitMap(n, 0);
        return;
    }   
 
    if (n == 2) {
        if (E == 31) {
            InitMap(n, 0);
            return;
        }   
        else {
            InitMap(n, 1);
            MakeMap(0, 1);
            return;
        }   
    }
    */ 

    vector <int> pw(V);
    for (int i = 0; i < E; ++i) {
        ++pw[C[i]];
        ++pw[D[i]];
        g[C[i]][D[i]] = g[D[i]][C[i]] = 1;
    }
    
    vector <int> ord;
    for (int i = 0; i < V; ++i)
        ord.app(i);
    auto comp = [&](int u, int v) {
        return pw[u] < pw[v];
    };
    sort(all(ord), comp);
 
    int mx = ord.back();
 
    //cout << "mx " << mx << ' ' << pw[mx] << endl;
 
    int sec = -1;
    for (int i = 0; i < V; ++i) {
        if (i != mx && !g[i][mx]) {
            sec = i;
            break;
        }   
    }   
 
    //cout << "sec " << sec << ' ' << pw[sec] << endl;
 
    vector <int> bit;
    for (int i = 0; i < V; ++i) {
        if (g[i][sec]) {
            bit.app(i);
        }   
    }   
    
    //cout << "bit " << bit.size() << endl;
 
    for (int i = 0; i < bit.size(); ++i) {
        if (!g[bit[i]][mx]) {
            swap(bit[0], bit[i]);
            //cout << "swap" << endl;
            break;
        }
    }   
 
    for (int i = 1; i < bit.size(); ++i) {
        int prv = bit[i-1];
        for (int j = i; j < bit.size(); ++j) {
            if (g[prv][bit[j]]) {
                swap(bit[i], bit[j]);
                break;
            }   
        }   
    }   
 
    vector <int> real;
    for (int i = 0; i < V; ++i) {
        if (!g[i][sec] && i != sec && i != mx)
            real.app(i);
    }   
 
    //cout << "real " << real.size() << endl;
 
    vector <int> num;
    for (auto e : real) {
        int x = 0;
        for (int i = 0; i < 10; ++i)
            if (g[e][bit[i]])
                x += 1 << i;
        num.app(x);
    }   
 
    /*
    InitMap( 3, 2 );
    MakeMap( 1, 2 );
    MakeMap( 1, 3 );
    */
 
    vector <ii> ans;
    for (int i = 0; i < real.size(); ++i)   
        for (int j = i+1; j < real.size(); ++j)
            if (g[real[i]][real[j]]) {
 
                //cout << "add " << num[i] << ' ' << num[j] << endl;
 
                ans.app(mp(num[i], num[j]));
            }
    InitMap(n, ans.size());
    for (auto e : ans)
        MakeMap(e.f, e.s);
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < bit.size(); ++j) {
                         ~~^~~~~~~~~~~~
Bob.cpp:119:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < real.size(); ++i)   
                     ~~^~~~~~~~~~~~~
Bob.cpp:120:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i+1; j < real.size(); ++j)
                           ~~^~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6912 KB Output is correct
2 Correct 15 ms 6912 KB Output is correct
3 Correct 13 ms 6912 KB Output is correct
4 Incorrect 13 ms 6912 KB Wrong Answer [11]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6912 KB Output is correct
2 Correct 15 ms 6912 KB Output is correct
3 Correct 13 ms 6912 KB Output is correct
4 Incorrect 13 ms 6912 KB Wrong Answer [11]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 11624 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -