| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1289128 | takoshanava | 항공 노선도 (JOI18_airline) | C++20 | 0 ms | 0 KiB |
#include "Alicelib.h"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
// void InitG( int V, int U )
// This function specifies the number of vertices of G and the number of edges of G.
// void MakeG( int pos, int C, int D )
// This function specifies the edges of G.
void Alice(int n, int m, int a[], int b[]){
vector<pair<int, int>> res;
for(int i = 0; i < m; i++) res.pb({a[i], b[i]});
for(int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
if (i & (1 << j)) res.pb({i, n + j});
}
}
for(int i = 0; i < 10; i++) res.pb({n + i, n + 10});
for(int i = 0; i < n + 10; i++) res.pb({i, n + 11});
for(int i = 0; i < 9; i++) res.pb({n + i, n + i + 1});
InitG(n + 12, res.size());
for(int i = 0; i < res.size(); i++) MakeG(i, res[i].fs, res[i].sc);
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
//void InitMap( int N, int M )
//This function specifies the number of islands of JOI Kingdom, and the number of airline routes in JOI Kingdom
//void MakeMap( int A, int B )
//This function specifies the number of airline routes in JOI Kingdom
void Bob(int n, int m, int c[], int d[]){
vector<int> deg(n, 0);
for(int i = 0; i < m; i++) deg[c[i]]++, deg[d[i]]++;
int ft, mx = -1, par, nd = -1, d1 = 0, d2 = 0;
vector<vector<bool> > gr(n, vector<bool>(n, 0));
for(int i = 0; i < n; i++) {
if(deg[i] > mx) mx = deg[i], ft = i;
}
for(int i = 0; i < m; i++) gr[c[i]][d[i]] = gr[d[i]][c[i]] = 1;
for(int i = 0; i < n; i++) {
if(!gr[i][ft] and i != ft) par = i;
}
for(int i = 0; i < n; i++) {
if(gr[par][i]){
int cnt = 0;
for(int j = 0; j < n; j++) {
if(gr[par][j] and gr[i][j]) cnt++;
}
if(cnt == 1)nd = i;
}
}
vector<bool> vis(n, 0);
vector<int> vect;
bool ok = 1;
while(ok){
vect.pb(nd);
vis[nd] = 1;
ok = 0;
for(int i = 0; i < n; i++) {
if(gr[i][nd] and !vis[i] and gr[par][i]){
nd = i, ok = 1;
break;
}
}
}
for(int i = 0; i < n; i++) d1 += gr[vect[0]][i], d2 += gr[vect[9]][i];
if(d1 < d2) reverse(vect.begin(), vect.end());
vector<pair<int, int>> ans;
for(int i = 0; i < m; i++){
if(!gr[par][c[i]] and !gr[par][d[i]] and c[i] != ft and d[i] != ft and c[i] != par and d[i] != par){
int a = 0, b = 0;
for(int j = 0; j < 10; j++) {
if(gr[c[i]][vect[j]]) a += (1<<j);
}
for (int j = 0; j < 10; j++) {
if(gr[d[i]][vect[j]]) b += (1<<j);
}
ans.pb({a, b});
}
}
InitMap(n - 12, ans.size());
for (auto a :ans) MakeMap(a.fs, a.sc);
}