Submission #719137

#	Time	Username	Problem	Language	Result	Execution time	Memory
719137		lam	Airline Route Map (JOI18_airline)	C++14	100 / 100	654 ms	29320 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
inline bool checkbit(int i, int j)
{
    return i>>j&1;
}
void Alice( int N, int M, int A[], int B[] ){
    int n,m;
    n=N; m=M;
    vector <ii> edges;
    for (int i=0; i<m; i++) edges.push_back({A[i],B[i]});
    for (int i=0; i<10; i++)
    {
        for (int j=0; j<n; j++) if (checkbit(j,i)) edges.push_back({n+i,j});
        if (i>0) edges.push_back({n+i,n+i-1});
    }
    for (int i=0; i<n; i++) edges.push_back({n+10,i});
    edges.push_back({n+10,n+11});
    InitG(n+12,edges.size());
    int cnt=0;
    for (ii i:edges) MakeG(cnt++,i.ff,i.ss);
}

Bob

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

void Bob( int V, int U, int C[], int D[] ){
    int n,m;
    n=V - 12;
    vector <vector<int>> adj(V);
    for (int i=0; i<U; i++)
    {
        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }
//    cerr<<V<<endl;
//    for (int i=0; i<V; i++)
//    {
//        cerr<<i<<" := ";
//        for (int j:adj[i]) cerr<<j<<' '; cerr<<endl;
//    }
    int type1,type2;
    for (int i=0; i<V; i++) if (adj[i].size()==1&&adj[adj[i][0]].size()==n+1)
    {
        type2 = i;
        type1 = adj[i][0];
    }
    vector <int> type(V,0);
    type[type2] = type[type1] = 2;
    for (int i:adj[type1]) if (i!=type2) type[i] = 1;
    vector <int> nodes;
    vector <vector<int>> sub_adj(V);
    for (int i=0; i<V; i++) if (type[i]==0) nodes.push_back(i);
    for (int i:nodes)
        for (int j:adj[i])
            if (type[j]==0) sub_adj[i].push_back(j);
//    for (int i=0; i<V; i++)
//    {
//        cerr<<i<<" := ";
//        for (int j:sub_adj[i]) cerr<<j<<' '; cerr<<endl;
//    }
    int it = -1;
    for (int i:nodes)
        if (sub_adj[i].size()==1)
    {
        if (it==-1||adj[it].size() < adj[i].size()) it = i;
    }
    vector <int> path;
    path.push_back(it);
    int p=-1;
    for (int i=1; i<10; i++)
        for (int j:sub_adj[it]) if (j!=p)
        {
            p = it;
            it = j;
            path.push_back(it);
            break;
        }
//    for (int i:nodes) cerr<<i<<' '; cerr<<"!!"<<endl;
//    cerr<<type1<<' '<<type2<<" = "; for (int i:path) cerr<<i<<' '; cerr<<endl;
    vector <int> inv_path(V);
    for (int i=0; i<10; i++) inv_path[path[i]] = i;
    vector <int> final_id(V);
    vector <vector<bool>> has_edge;
    has_edge.assign(10,vector<bool>(V,0));
    for (int i=0; i<U; i++)
    {
        int u=C[i]; int v=D[i];
        if (type[u] == 0 && type[v] == 1)
            has_edge[inv_path[u]][v] = 1;
        swap(u,v);
        if (type[u] == 0 && type[v] == 1)
            has_edge[inv_path[u]][v] = 1;
    }
    for (int i=0; i<V; i++) if (type[i] == 1)
    {
        for (int j=0; j<10; j++) if (has_edge[j][i]) final_id[i] |= (1<<j);
    }
    vector <pair<int,int>> edges;
    for (int i=0; i<U; i++)
    {
        int u=C[i]; int v=D[i];
        if (type[u]==1&&type[v]==1)
        {
            edges.push_back({final_id[u],final_id[v]});
        }
    }
    InitMap(n,edges.size());
    for (pair<int,int> i:edges) MakeMap(i.first,i.second);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:24:72: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     for (int i=0; i<V; i++) if (adj[i].size()==1&&adj[adj[i][0]].size()==n+1)
      |                                                   ~~~~~~~~~~~~~~~~~~~~~^~~~~
Bob.cpp:9:11: warning: unused variable 'm' [-Wunused-variable]
    9 |     int n,m;
      |           ^
Bob.cpp:30:15: warning: 'type2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     type[type2] = type[type1] = 2;
      |               ^
Bob.cpp:30:29: warning: 'type1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     type[type2] = type[type1] = 2;
      |                             ^

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63