oj.uz

Submission #207191

# Submission time Handle Problem Language Result Execution time Memory
207191 2020-03-06T16:15:40 Z nvmdava Airline Route Map (JOI18_airline) C++17
0 / 100
 652 ms 31040 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int> > e;

void Alice( int N, int M, int A[], int B[] ){

	for(int i = 0; i < M; ++i)
		e.push_back({A[i], B[i]});

	for(int j = 0; j < 10; ++j)
		for(int i = 0; i < N; ++i)
			if(i & (1 << j))
				e.push_back({N + j, i});
	
	for(int i = 1; i <= 9; ++i){
		for(int j = i + 1; j <= 9; ++j){
			if(i + j >= 10){
				e.push_back({N + i, N + j});
			}
		}
	}
	e.push_back({N + 0, N + 5});
	for(int i = 0; i < N + 10; ++i)
		e.push_back({N + 10, i});
	for(int i = 0; i < 10; ++i)
		e.push_back({N + 11, N + i});

	InitG(N + 12, e.size());
	int t = 0;
	for(auto& x : e)
		MakeG(t++, x.first, x.second);
}


#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define N 1505

int deg[N], id[N];

bool adj[N][N];
vector<pair<int, int> > v;

void Bob( int V, int U, int C[], int D[] ){

	for(int i = 0; i < U; ++i){
		++deg[D[i]];
		++deg[C[i]];
		adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
	}

	int r, t;
	for(int i = 0; i < V; ++i)
		if(deg[i] == V - 2)
			r = i;
	

	for(int i = 0; i < V; ++i)
		if(r != i && !adj[r][i])
			t = i;

	id[r] = id[t] = -1;
	for(int x : adj[t]){
		v.push_back({0, x});
	}

	for(int i = 0; i < 10; ++i){
		for(int j = 0; j < 10; ++j){
			v[i].ff += adj[v[i].ss][v[j].ss];
		}
		id[v[i].ss] = -1;
	}
	sort(v.begin(), v.end());

	if(adj[v[0].ss][v[9].ss])
		swap(v[1], v[0]);
	if(adj[v[0].ss][v[6].ss])
		swap(v[6], v[5]);

	for(int i = 0; i < 10; ++i)
		for(int x = 0; x < V; ++x)
			if(adj[x][v[i].ss] && id[x] != -1)
			id[x] |= 1 << i;
		
	int cnt = 0;
	for(int i = 0; i < U; ++i){
		C[i] = id[C[i]];
		D[i] = id[D[i]];
		if(C[i] != -1 && D[i] != -1)
			++cnt;
	}
	InitMap(V - 12, cnt);
	for(int i = 0; i < U; ++i)
		if(C[i] != -1 && D[i] != -1)
			MakeMap(C[i], D[i]);
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:31:8: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  id[r] = id[t] = -1;
  ~~~~~~^~~~~~~~~~~~
Bob.cpp:21:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int r, t;
         ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 6640 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 6640 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 652 ms 31040 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -