oj.uz

Submission #185442

# Submission time Handle Problem Language Result Execution time Memory
185442 2020-01-11T18:18:44 Z Akashi Airline Route Map (JOI18_airline) C++14
0 / 100
 943 ms 35272 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

struct usu{
    int pos, x, y;
};

const int LG = 9;
vector <usu> edgeS;
void add_edge(int pos, int x, int y){
    edgeS.push_back({pos, x, y});
}

void Alice( int n, int m, int a[], int b[] ){
    for(int i = 0; i < m ; ++i) add_edge(i, a[i], b[i]);

    int nr = m - 1;
    for(int i = n; i <= n + LG ; ++i){
        add_edge(++nr, i, n + 10);
        add_edge(++nr, i, n + 11);
        if(i != n + LG) add_edge(++nr, i, i + 1);
    }
    for(int i = 0; i < n ; ++i){
        add_edge(++nr, i, n + 11);
        for(int j = 0; j <= LG ; ++j){
            if((1 << j) & i) add_edge(++nr, i, n + j + 1);
        }
    }

    InitG(n + 12, edgeS.size());
    for(auto it : edgeS) MakeG(it.pos, it.x, it.y);
}



#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

const int LG = 9;
int real_n;
int gr[1025], exp_gr[1025];
int real_id[1025];
bool viz[1025], ap[1025];
vector <int> v[1025];
vector <pair <int, int> > edges;

void find_bits(int n, int wh, int p){
    for(auto it : v[wh]){
        ap[it] = 1;
        v[it].erase(find(v[it].begin(), v[it].end(), wh));
        v[it].erase(find(v[it].begin(), v[it].end(), p));
        gr[it] -= 2;
    }
    int nr = LG;
    while(nr >= 0){
        int aux;
        for(auto nod : v[wh]){
            if(!ap[nod]) continue ;
            int cnt = 0;
            for(auto it : v[nod]) if(ap[it]) ++cnt;

            if(cnt <= 1 && gr[nod] - cnt == exp_gr[nr]){
                ap[nod] = 0;
                aux = nod;
                real_id[nod] = nr + real_n;
                break ;
            }
        }

        for(auto nod : v[wh]){
            if(find(v[nod].begin(), v[nod].end(), aux) != v[nod].end()){
                v[nod].erase(find(v[nod].begin(), v[nod].end(), aux));
                v[aux].erase(find(v[aux].begin(), v[aux].end(), nod));
                --gr[nod]; --gr[aux];
                break ;
            }
        }
        --nr;
    }

}

void Bob( int n, int m, int C[], int D[] ){
    real_n = n - 12;
    for(int i = 0; i < real_n ; ++i){
        for(int j = 0; j <= LG ; ++j)
            if((1 << j) & i) ++exp_gr[j];
    }

    for(int i = 0; i < m ; ++i){
        ++gr[C[i]];
        ++gr[D[i]];
        v[C[i]].push_back(D[i]);
        v[D[i]].push_back(C[i]);
    }

    int p, wh;
    for(int i = 0; i < n ; ++i) if(gr[i] == n - 2) {real_id[i] = n - 2; p = i; break ;}

    viz[p] = 1;
    for(auto it : v[p]) viz[it] = 1;
    for(int i = 0; i < n ; ++i) if(!viz[i]) {real_id[i] = n - 1; wh = i; break ;}

    memset(viz, 0, sizeof(viz));
    find_bits(n - 2, wh, p);

    for(auto nod : v[wh]){
        if(nod == p) continue ;
        int ad = real_id[nod] - real_n;
        int p = (1 << ad);
        for(auto it : v[nod]) real_id[it] += p;
    }

    for(int i = 0; i < n ; ++i){
        if(real_id[i] >= real_n) continue ;
        for(auto it : v[i]){
            if(real_id[i] < real_id[it] && real_id[it] < real_n)
                edges.push_back({real_id[i], real_id[it]});
        }
    }

    InitMap(real_n, edges.size());
    for(auto it : edges) MakeMap(it.first, it.second);
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:66:12: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
     viz[p] = 1;
     ~~~~~~~^~~
Bob.cpp:71:14: warning: 'wh' may be used uninitialized in this function [-Wmaybe-uninitialized]
     find_bits(n - 2, wh, p);
     ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6896 KB Output is correct
2 Correct 14 ms 6896 KB Output is correct
3 Correct 8 ms 6896 KB Output is correct
4 Correct 9 ms 6896 KB Output is correct
5 Correct 9 ms 6896 KB Output is correct
6 Correct 9 ms 6640 KB Output is correct
7 Correct 8 ms 6640 KB Output is correct
8 Correct 9 ms 6896 KB Output is correct
9 Correct 9 ms 6640 KB Output is correct
10 Correct 9 ms 6640 KB Output is correct
11 Correct 8 ms 6896 KB Output is correct
12 Correct 9 ms 6896 KB Output is correct
13 Correct 9 ms 6640 KB Output is correct
14 Correct 9 ms 6896 KB Output is correct
15 Correct 11 ms 6896 KB Output is correct
16 Correct 9 ms 6896 KB Output is correct
17 Correct 8 ms 6736 KB Output is correct
18 Correct 8 ms 6640 KB Output is correct
19 Correct 9 ms 7152 KB Output is correct
20 Correct 10 ms 6896 KB Output is correct
21 Correct 9 ms 6896 KB Output is correct
22 Failed 9 ms 6640 KB Wrong Answer [13]
23 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6896 KB Output is correct
2 Correct 14 ms 6896 KB Output is correct
3 Correct 8 ms 6896 KB Output is correct
4 Correct 9 ms 6896 KB Output is correct
5 Correct 9 ms 6896 KB Output is correct
6 Correct 9 ms 6640 KB Output is correct
7 Correct 8 ms 6640 KB Output is correct
8 Correct 9 ms 6896 KB Output is correct
9 Correct 9 ms 6640 KB Output is correct
10 Correct 9 ms 6640 KB Output is correct
11 Correct 8 ms 6896 KB Output is correct
12 Correct 9 ms 6896 KB Output is correct
13 Correct 9 ms 6640 KB Output is correct
14 Correct 9 ms 6896 KB Output is correct
15 Correct 11 ms 6896 KB Output is correct
16 Correct 9 ms 6896 KB Output is correct
17 Correct 8 ms 6736 KB Output is correct
18 Correct 8 ms 6640 KB Output is correct
19 Correct 9 ms 7152 KB Output is correct
20 Correct 10 ms 6896 KB Output is correct
21 Correct 9 ms 6896 KB Output is correct
22 Failed 9 ms 6640 KB Wrong Answer [13]
23 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

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