oj.uz

Submission #48561

# Submission time Handle Problem Language Result Execution time Memory
48561 2018-05-16T11:02:02 Z ngkan146 Airline Route Map (JOI18_airline) C++11
0 / 100
 693 ms 30888 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> GG[1505];
void Alice(int n, int m, int a[], int b[]){
    for(int i=0;i<m;i++){
        GG[a[i]+1].push_back(b[i]+1);
        GG[b[i]+1].push_back(a[i]+1);
    }

    for(int i=1;i<=n;i++){
        for(int bit=0;bit<10;bit++){
            if (((i>>bit) & 1))
                GG[i].push_back(n+bit+1),
                GG[n+bit+1].push_back(i);
        }
    }
    // num 11
    for(int i=n+1;i<=n+10;i++){
        GG[n+11].push_back(i);
        GG[i].push_back(n+11);
    }
    // num 12
    for(int i=1;i<=n+10;i++){
        GG[i].push_back(n+12);
        GG[n+12].push_back(i);
    }

    for(int i=1;i<=9;i++){
        GG[n+i].push_back(n+i+1);
        GG[n+i+1].push_back(i);
    }
    for(int i=2;i<=8;i++){
        GG[n+i].push_back(n+10);
        GG[n+10].push_back(n+i);
    }

    int numV = n+12;
    int numE = 0;
    for(int i=1;i<=n+12;i++){
        numE += GG[i].size();
    }
    InitG(numV, numE/2);
    numE = 0;
    for(int i=1;i<=n+12;i++){
        for(auto v: GG[i]){
            if (i < v)
                MakeG(numE++, i-1, v-1);
        }
    }
}


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

vector <int> G[1505];
int isbit[1505];
int num[15];
vector <int> Gbit[1505];
set <int> s;
int mask[1505];
void Bob( int n, int m, int C[], int D[] ){
    for(int i=0;i<m;i++){
        G[C[i]+1].push_back(D[i]+1);
        G[D[i]+1].push_back(C[i]+1);
    }
    // find num 12
    for(int i=1;i<=n;i++){
        if (G[i].size() == n-2)
            num[12] = i;
    }
    // find num11
    for(int i=1;i<=n;i++){
        if (i == num[12]) continue;
        bool ok = 1;
        for(auto v: G[i])
            ok &= (v != num[12]);
        if (ok)
            num[11] = i;
    }
    // find lst;
    vector <int> bitlst;
    for(auto v: G[num[11]]){
        if (v != num[12]){
            isbit[v] = 1;
            bitlst.push_back(v);
        }
    }

    for(auto u: bitlst){
        for(auto v:G[u]){
            if (!isbit[v])  continue;
            Gbit[u].push_back(v);
        }
    }
    // find num1
    for(auto v: bitlst){
        if (Gbit[v].size() == 2)
            num[1] = v;
    }
    // find num2 -> 9
    for(int cur=1;cur<9;cur++){
        for(auto v: Gbit[num[cur]]){
            if (v != num[cur] && G[v].size() < 9){
                num[cur+1] = v;
            }
        }
    }
    set <int> used;
    for(int i=1;i<=12;i++){
        if (i != 10)    used.insert(num[i]);
    }

    // find num 10
    for(auto v: bitlst){
        if (!used.count(v)){
            num[10] = v;
            used.insert(v);
        }
    }

    for(int i=1;i<=10;i++){
        for(auto v: G[num[i]]){
            if (!used.count(v))
                mask[v] |= (1<<(i-1));
        }
    }
    int newV = n - 12;
    int newE = 0;
    for(int i=1;i<=n;i++){
        if (!mask[i])   continue;
        for(auto v: G[i]){
            newE += (!mask[v]);
        }
    }

	InitMap( newV, newE/2 );

	for(int i=1;i<=n;i++){
        if (!mask[i])  continue;
        for(auto v: G[i]){
            if (!mask[i])  continue;
            if (mask[i] < mask[v])
                MakeMap(mask[i]-1, mask[v]-1);
        }
	}
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:18:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (G[i].size() == n-2)
             ~~~~~~~~~~~~^~~~~~

Subtask #1
0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

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