oj.uz

Submission #242836

# Submission time Handle Problem Language Result Execution time Memory
242836 2020-06-29T11:06:28 Z osaaateiasavtnl Airline Route Map (JOI18_airline) C++14
0 / 100
 738 ms 30768 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];
    }   

    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];
 
vector <ii> solve(int V, int E, int C[], int D[], int mx) {
    int sec = -1;
    for (int i = 0; i < V; ++i) {

        int pw = 0;
        for (int j = 0; j < V; ++j)
            pw += g[i][j];

        if (pw != 10)
            continue;

        if (i != mx && !g[i][mx]) {
            sec = i;
            break;
        }   
    }   

    if (sec == -1) {
        vector <ii> ans;
        ans.app({V, V});
        return ans;
    }
 
    //cout << "sec " << sec << ' ' << pw[sec] << endl;
 
    vector <int> bit;
    for (int i = 0; i < V; ++i) {
        if (g[i][sec]) {
            bit.app(i);
        }   
    }   

    if (bit.size() != 10) {
        vector <ii> ans;
        ans.app({V, V});
        return ans;
    }   
    //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]));
            }
    return ans;
}

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;
    }
        
    int mx_pw = 0;
    for (int u = 0; u < V; ++u)
        mx_pw = max(mx_pw, pw[u]);

    int ht = 0;

    for (int u = 0; u < V; ++u) {
        if (pw[u] = mx_pw) {

            ++ht;
            if (ht > 2)
                exit(1);

            auto ans = solve(V, E, C, D, u);

            bool ban = 0;
            for (auto e : ans) {
                if (e.f == e.s || e.f >= n || e.s >= n) {
                    ban = 1;
                    break;
                }   
            }   

            if (!ban) {
                InitMap(n, ans.size());
                for (auto e : ans)
                    MakeMap(e.f, e.s);
                return;
            }
        }   
    }    
}

Compilation message

Bob.cpp: In function 'std::vector<std::pair<int, int> > solve(int, int, int*, int*, int)':
Bob.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < bit.size(); ++j) {
                         ~~^~~~~~~~~~~~
Bob.cpp:98:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < real.size(); ++i)   
                     ~~^~~~~~~~~~~~~
Bob.cpp:99:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i+1; j < real.size(); ++j)
                           ~~^~~~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:126:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         if (pw[u] = mx_pw) {

Subtask #1
0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

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