제출 #374086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374086		i_am_noob	Airline Route Map (JOI18_airline)	C++17	100 / 100	891 ms	29804 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))

void Alice( int n, int m, int a[], int b[] ){
	//InitG( 3, 2 );
	//MakeG( 1, 2 );
	//MakeG( 1, 3 );
	vector<pii> edges;
	rep(m) edges.pb({a[i],b[i]});
	rep(n) rep1(j,10) if(i&pow2(j)) edges.pb({i,n+j});
	rep(9) edges.pb({n+i,n+i+1});
	rep(n) edges.pb({i,n+10});
	rep(10) edges.pb({n+i,n+10}),edges.pb({n+i,n+11});
	InitG(n+12,sz(edges));
	rep(sz(edges)) MakeG(i,edges[i].first,edges[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define maxn 1505

static bool vis[maxn];
static vector<int> adj[maxn],vec,vec1;
static void dfs(int u, int par){
	vec.pb(u);
	for(auto v: adj[u]) if(v!=par&&vis[v]) dfs(v,u);
}

void Bob( int n, int m, int a[], int b[] ){
	//InitMap( 3, 2 );
	//MakeMap( 1, 2 );
	//MakeMap( 1, 3 );
	int deg[maxn],deg2[maxn],val[maxn],id[maxn];
	memset(deg,0,sizeof deg);
	rep(m) deg[a[i]]++,deg[b[i]]++;
	rep(m) adj[a[i]].pb(b[i]),adj[b[i]].pb(a[i]);
	int x=max_element(deg,deg+maxn)-deg,y;
	memset(vis,0,sizeof vis);
	for(auto v: adj[x]) vis[v]=1;
	rep(n) if(x!=i&&!vis[i]) y=i;
	memset(vis,0,sizeof vis);
	for(auto v: adj[y]) vis[v]=1;
	for(auto v: adj[y]) deg2[v]=0;
	rep(m) if(vis[a[i]]&&vis[b[i]]) deg2[a[i]]++,deg2[b[i]]++;
	for(auto v: adj[y]) if(deg2[v]==1) vec1.pb(v);
	if(deg[vec1[0]]>deg[vec1[1]]) dfs(vec1[0],-1);
	else dfs(vec1[1],-1);
	rep(10) val[vec[i]]=i;
	rep(n) if(i!=x&&i!=y&&!vis[i]){
		id[i]=0;
		for(auto v: adj[i]){
			if(vis[v]) id[i]+=1<<val[v];
		}
		//cout << id[i] << "\n";
	}
	vector<pii> edges;
	rep(m) if(a[i]!=x&&a[i]!=y&&(!vis[a[i]])&&b[i]!=x&&b[i]!=y&&(!vis[b[i]])) edges.pb({id[a[i]],id[b[i]]});
	InitMap(n-12,sz(edges));
	//for(auto& [x,y]: edges) cout << x << ' ' << y << "\n";
	for(auto& [x,y]: edges) MakeMap(x,y);
}

컴파일 시 표준 에러 (stderr) 메시지

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:52:51: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |  rep(m) if(a[i]!=x&&a[i]!=y&&(!vis[a[i]])&&b[i]!=x&&b[i]!=y&&(!vis[b[i]])) edges.pb({id[a[i]],id[b[i]]});
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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