oj.uz

Submission #242790

# Submission time Handle Problem Language Result Execution time Memory
242790 2020-06-29T10:22:57 Z osaaateiasavtnl Airline Route Map (JOI18_airline) C++17
0 / 100
 639 ms 30728 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[] ){   
    /*
    InitG( 3, 2 );
    MakeG( 1, 2 );
    MakeG( 1, 3 );
    */
 
    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));
  
    InitG(N + 12, ans.size());
    int ptr = 0;
    for (auto e : ans) {
        MakeG(ptr++, e.f, e.s);
        //cout << e.f << ' ' << e.s << endl;
    }
}
 
#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;
    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:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:67:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < bit.size(); ++j) {
                         ~~^~~~~~~~~~~~
Bob.cpp:99:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < real.size(); ++i)   
                     ~~^~~~~~~~~~~~~
Bob.cpp:100: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 13 ms 6912 KB Output is correct
2 Correct 13 ms 6760 KB Output is correct
3 Incorrect 13 ms 6912 KB Wrong Answer [12]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 639 ms 30728 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -