oj.uz

답안 #56715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56715 2018-07-12T08:39:48 Z 정원준(#1619) 항공 노선도 (JOI18_airline) C++11
0 / 100
 455 ms 15464 KB 
#include <Alicelib.h>
#include <bits/stdc++.h>
#define L long long

using namespace std;

void InitG(int v,int u);
void MakeG(int pos,int c,int d);
void Alice(int n,int m,int a[],int b[]);

vector<int>a,b;

void Alice(int n,int m,int aa[],int bb[]){
	int i,j;
	for(i=0;i<m;i++)
	{
		a.push_back(aa[i]);
		b.push_back(bb[i]);
	}
	vector<int>s,e;
	for(i=0;i<10;i++)
	{
		for(j=0;j<n;j++)
		{
			if((j+1)&(1<<i))
			{
				a.push_back(i+n);
				b.push_back(j);
			}
		}
	}
	
	
	for(i=0;i<10;i++)
	{
		a.push_back(n+12);
		b.push_back(i+n);
	}
	for(i=0;i<n;i++)
	{
		a.push_back(n+12);
		b.push_back(i);
	}
	
	for(i=1;i<10;i++)
	{
		a.push_back(n+11);
		b.push_back(n+i);
	}
	
	for(i=0;i<8;i++)
	{
		a.push_back(n+i);
		b.push_back(n+i+1);
	}
	for(i=2;i<10;i++)
	{
		a.push_back(n);
		b.push_back(n+i);
	}
	
	InitG(n+12,a.size());
	for(i=0;i<a.size();i++)
	{
		MakeG(i,a[i],b[i]);
	}
}

#include <Boblib.h>
#include <bits/stdc++.h>
#define L long long

using namespace std;

void InitMap(int n,int m);
void MakeMap(int a,int b);
void Bob(int v,int u,int c[],int d[]);

int cnt[1111];
int trans[1111];
int ih[1111][1111];
int bits[10];
int chkbit[1111];
int ordered[1111];
int node[1111];
vector<int>vec[1111];
int vertexes;
int edges;

	vector<int>c;
	vector<int>d;
	
int deg_in_9(int x){
	int i,ret=0;
	for(i=0;i<vec[x].size();i++)
	{
		if(chkbit[vec[x][i]]) ret++;
	}
	return ret;
}

void Bob(int v,int u,int cc[],int dd[]){
	int i,j;
	for(i=0;i<u;i++)
	{
		c.push_back(cc[i]);
		d.push_back(dd[i]);
	}
	for(i=0;i<u;i++)
	{
		vec[c[i]].push_back(d[i]);
		vec[d[i]].push_back(c[i]);
		cnt[c[i]]++;
		cnt[d[i]]++;
		ih[c[i]][d[i]]=ih[d[i]][c[i]]=1;
	}
	int ma=0,ind,point0,zero,nine;
	for(i=0;i<v;i++)
	{
		if(cnt[i]>ma)
		{
			ma=cnt[i];
			ind=i;
		}
	}
	for(i=0;i<v;i++)
	{
		if(!ih[ind][i]) point0=i;
	}
	
	for(i=0;i<9;i++)
	{
		chkbit[vec[point0][i]]=1;
	}
	
	for(i=0;i<v;i++)
	{
		if(i!=ind&&deg_in_9(i)==8)
		{
			zero=i;
		}
	}
	bits[0]=zero;
	chkbit[zero]=1;
	ordered[zero]=1;
	for(i=0;i<9;i++)
	{
		if(deg_in_9(vec[point0][i])==1)
		{
			nine=vec[point0][i];
		}
	}
	int temp=nine;
	ordered[nine]=1;
	bits[9]=nine;
	for(i=8;i>=1;i--)
	{
		for(j=0;j<vec[temp].size();j++)
		{
			if(!ordered[vec[temp][j]]&&chkbit[vec[temp][j]])
			{
				temp=vec[temp][j];
				break;
			}
		}
		ordered[temp]=1;
		bits[i]=temp;
	}
	for(i=0;i<v;i++)
	{
		if(i!=ind&&!chkbit[i])
		{
			node[i]=1;
			vertexes++;
			int val=0;
			for(j=0;j<10;j++)
			{
				if(ih[i][bits[j]])
				{
					val+=(1<<j);
				}
			}
			trans[i]=val-1;
		}
	}
	for(i=0;i<u;i++)
	{
		if(node[c[i]]&&node[d[i]])
		{
			edges++;
		}
	}
	InitMap(vertexes,edges);
	for(i=0;i<u;i++)
	{
		if(node[c[i]]&&node[d[i]])
		{
			MakeMap(trans[c[i]],trans[d[i]]);
		}
	}
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:63:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<a.size();i++)
          ~^~~~~~~~~

Bob.cpp: In function 'int deg_in_9(int)':
Bob.cpp:27:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vec[x].size();i++)
          ~^~~~~~~~~~~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:90:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vec[temp].size();j++)
           ~^~~~~~~~~~~~~~~~~
Bob.cpp:86:15: warning: 'nine' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ordered[nine]=1;
  ~~~~~~~~~~~~~^~
Bob.cpp:77:15: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ordered[zero]=1;
  ~~~~~~~~~~~~~^~
Bob.cpp:103:3: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(i!=ind&&!chkbit[i])
   ^~
Bob.cpp:49:15: warning: 'point0' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ma=0,ind,point0,zero,nine;
               ^~~~~~

Subtask #1
0 / 22.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 63.0

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