제출 #1304588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304588		vako_p	항공 노선도 (JOI18_airline)	C++20	100 / 100	178 ms	32508 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second


void Alice( int N, int M, int A[], int B[] ){
  static ll n,m;
  n = N;
  m = M;
  vector<pair<ll,ll>> ans;
  for(int i = 0; i < m; i++) ans.pb({A[i], B[i]});
  for(int i = 0; i < n + 10; i++) ans.pb({n + 10, i});
  for(int i = n; i < n + 10; i++) ans.pb({n + 11, i});
  for(int i = 0; i < n; i++){
    for(int bit = 0; bit < 10; bit++){
      if((1 << bit) & i) ans.pb({i, n + bit});
    }
  }
  for(int i = n + 2; i < n + 10; i++) ans.pb({i, i - 1});
  for(int i = n + 2; i < n + 10; i++) ans.pb({n, i});
  InitG(n + 12, ans.size());
  ll cc = 0;
  for(auto it : ans) MakeG(cc++, it.ff, it.sd);
  
  // for(auto it : ans) cout << it.ff << ' ' << it.sd << endl;
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second

static const int mxN = 2005;
static bool vis1[mxN],vis[mxN],edge[mxN][mxN];
static vector<ll> v[mxN];

void Bob( int V, int U, int C[], int D[] ){
  static ll n,m;
  vector<ll> bit(20, -1),val(mxN,0LL);
  n = V;
  m = U;
  for(int i = 0; i < m; i++){
    v[C[i]].pb(D[i]);
    v[D[i]].pb(C[i]);
    edge[C[i]][D[i]] = edge[D[i]][C[i]] = true;
  }
  ll st = 0;
  for(int i = 0; i < n; i++){
    if(v[i].size() == n - 2) st = i;
    // else assert(v[i].size() < n - 2);
  } 

  // cout << " --> " << st << endl;

  vis1[st] = true;
  vis[st] = true;
  for(auto it : v[st]) vis1[it] = true;
  for(int i = 0; i < n; i++){
    if(!vis1[i]) st = i;
  } 

  // cout << " --> " << st << ' ' << v[st].size() << endl;

  // for(int i = 0; i < n; i++) vis1[i] = false;
  vis[st] = true;
  vector<ll> vv;
  for(auto it : v[st]){
    vv.pb(it);
    // vis[it] = true;
  } 
  for(auto at : vv){
    ll ok = 2;
    for(auto it : vv){
      if(it == at) continue;
      if(!edge[it][at]){
        ok--;
        bit[1] = it;
      } 
    }
    if(ok > 0){
      bit[0] = at;
      break;
    } 
  }
  // cout << bit[0] << ' ' << bit[1] << endl;
  vis[bit[0]] = vis[bit[1]] = true;
  for(int i = 2; i < 10; i++){
    for(auto it : vv){
      if(edge[it][bit[i - 1]] and !vis[it]){
        vis[it] = true;
        bit[i] = it;
        break;
      }
    }
  }

  // for(int i = 0; i < n; i++){
    // for(int j = 0; j < n; j++) cout << edge[i][j] << ' ';
    // cout << endl;
  // }

  // for(auto it : vv) cout << it << ' ';
  // cout << endl;
  
  // for(int i = 0; i < 10; i++) cout << bit[i] << ' ' << v[bit[i]].size() << endl;
  // cout << endl;

  vector<pair<ll,ll>> ans;
  for(int i = 0; i < n; i++){
    if(vis[i]) continue;
    val[i] = 0;
    for(int j = 0; j < 10; j++) if(edge[bit[j]][i]) val[i] += (1 << j);
    // cout << i << " ----> " << val[i] << endl;
  }
  for(int i = 0; i < n; i++){
    if(vis[i]) continue;
    for(auto it : v[i]) if(!vis[it] and i < it) ans.pb({val[i], val[it]});
  }
  // for(auto it : ans) cout << it.ff << ' ' << it.sd << endl;
  InitMap(n - 12, ans.size()); 
  for(auto it : ans) MakeMap(it.ff, it.sd);
}

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