oj.uz

답안 #313424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313424 2020-10-16T00:37:44 Z arthur_nascimento 항공 노선도 (JOI18_airline) C++14
0 / 100
 458 ms 11752 KB 
#include "Alicelib.h"
 
#include <cassert>
 
#include <cstdio>
 
#include <bits/stdc++.h>
 
#define maxn 1111
 
#define maxK 4100
 
#define ll long long
 
#define pb push_back
 
#define pii pair<int,int>
 
#define mod 1000000007 
 
#define debug(args...) //fprintf(stderr,args)
 
using namespace std;

#define dg dhbe
int dg[maxn];
 
void Alice( int N, int M, int A[], int B[] ){
 
 
	vector<pii> v;
 
	for(int i=0;i<M;i++)
		v.pb({A[i],B[i]}), dg[A[i]]++, dg[B[i]]++;
 
	for(int i=0;i<10;i++)
		for(int j=0;j<N;j++)
			if(j & (1<<i))
				v.pb({i+N,j}), dg[i+N]++, dg[j]++;
 
	for(int i=0;i<N+10;i++){
		if(i < N){
			v.pb({10+N,i}), dg[10+N]++, dg[i]++;
			v.pb({11+N,i}), dg[11+N]++, dg[i]++;
		}
		else if (i == N);
		else if(i < N + 5)
			v.pb({10+N,i}), dg[10+N]++, dg[i]++;
		else
			v.pb({11+N,i}), dg[11+N]++, dg[i]++;
	}
 
	for(int i=0;i<9;i++)
		v.pb({i+N,i+N+1}), dg[i+N]++, dg[i+N+1]++;

	vector<int> vv;
	for(int i=0;i<N+12;i++) vv.pb(dg[i]);
	//printf("N %d\n",N);
	sort(vv.begin(), vv.end());
	reverse(vv.begin(), vv.end());
	//for(int i=0;i<N+12;i++) printf("%d ",vv[i]); printf("\n");


	if(vv[0] != N + 5 || vv[1] != N + 4 || vv[2] >= N + 4) InitG(-1,-1);
 
	InitG(N+12,v.size());
 
	int bla = 0;
	
	for(pii i : v)
		MakeG(bla++, i.first,i.second);
	
 
}
#include "Boblib.h"
 
#include <cassert>
 
#include <cstdio>
 
#define maxn 1111
 
#include <bits/stdc++.h>
 
 
 
#define maxK 4100
 
#define ll long long
 
#define pb push_back
 
#define pii pair<int,int>
 
#define mod 1000000007 
 
#define debug(args...) fprintf(stderr,args)
 
using namespace std;
 
int mrk[maxn];
 
int dg[maxn];
 
vector<int> L[maxn];
 
int real_id[maxn];

int vis[maxn];
 
void go(int vx,int num,int p=-1){
	//if(vis[vx]) return;
	vis[vx] = 1;
	for(int i : L[vx])
		real_id[i] += num;
	debug("go %d with %d\n",vx,num);
	for(int i : L[vx])
		if(mrk[i] == 1 && i != p)
			go(i,2*num,vx);
}
 
 
void Bob( int V, int U, int C[], int D[] ){
 
	for(int i=0;i<V;i++) L[i].clear(), mrk[i] = dg[i] = vis[i] = 0;
 
	for(int i=0;i<U;i++){
		dg[C[i]]++, dg[D[i]]++;
		L[C[i]].pb(D[i]);
		L[D[i]].pb(C[i]);
	}
 
	vector<int> id;
	for(int i=0;i<V;i++)
		id.pb(i);
	sort(id.begin(), id.end(), [](int i,int j){
		return dg[i] > dg[j];
	});
 
	debug("id %d (%d), %d(%d)\n",id[0],dg[id[0]],id[1],dg[id[1]]);
 
	for(int i : L[id[0]])
		mrk[i]++;
	for(int i : L[id[1]])
		mrk[i]++;

	int n = V - 12;
	//assert(dg[id[0]] == n + 5 && dg[id[1]] == n + 4 && dg[id[2]] < n + 4);
 
	int ini = -1;
	for(int i=0;i<V;i++) if(mrk[i] == 0 && i != id[0] && i != id[1]){
		//assert(ini == -1);
		ini = i;
	}

	//assert(ini >= 0);
 
	go(ini,1);
 
	for(int i=0;i<V;i++)
		debug("mrk[%d] = %d, real_id = %d\n",i,mrk[i],real_id[i]);
 
	vector<pii> ans	;
	for(int i=0;i<U;i++)
		if(mrk[C[i]] == 2 && mrk[D[i]] == 2){
			debug("add %d %d -> %d %d\n",C[i],D[i],real_id[C[i]], real_id[D[i]]);
			ans.pb({real_id[C[i]], real_id[D[i]]});
		}
 
	InitMap( V - 12, ans.size() );
 
	for(pii i : ans)
 
		MakeMap( i.first, i.second );
 
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:73:6: warning: unused variable 'n' [-Wunused-variable]
   73 |  int n = V - 12;
      |      ^

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3456 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3456 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 458 ms 11752 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -