oj.uz

Submission #684826

# Submission time Handle Problem Language Result Execution time Memory
684826 2023-01-22T14:25:10 Z US3RN4M3 Airline Route Map (JOI18_airline) C++17
0 / 100
 522 ms 34896 KB 
#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
	vector<pair<int, int>> ans;
	for(int i = 0; i < M; i++) ans.push_back({A[i], B[i]});
	for(int i = 0; i < N + 12; i++) {
		if(i != N + 1 && i != N) ans.push_back({N, i});
	}
	for(int i = N + 2; i < N + 12; i++) {
		ans.push_back({N + 1, i});
	}
	for(int i = N + 4; i < N + 12; i++) {
		ans.push_back({N + 2, i});
	}
	for(int i = N + 3; i < N + 11; i++) {
		ans.push_back({i, i + 1});
	}
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < N; j++) if((j >> i) & 1) {
			ans.push_back({N + 2 + i, j});
		}
	}
	InitG(N + 12, ans.size());
	for(int i = 0; i < ans.size(); i++) MakeG(i, ans[i].first, ans[i].second);
}


#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
	vector<vector<int>> graph(V);
	for(int i = 0; i < U; i++) {
		graph[C[i]].push_back(D[i]);
		graph[D[i]].push_back(C[i]);
	}
	int head = 0;
	for(int i = 0; i < V; i++) if(graph[i].size() == V - 2) head = i;
	int head2 = 0;
	vector<bool> is_head2(V, true);
	is_head2[head] = false;
	for(int i : graph[head]) is_head2[i] = false;
	for(int i = 0; i < V; i++) if(is_head2[i]) head2 = i;
	vector<bool> is_head_extra(V, false);
	for(int i : graph[head2]) is_head_extra[i] = true;
	int heads[10];
	vector<int> opts;
	for(int i = 0; i < V; i++) if(is_head_extra[i]) opts.push_back(i);
	
	for(int i = 0; i < 10; i++) {
		int cnt = 0;
		for(int k : graph[opts[i]]) if(is_head_extra[k]) cnt++;
		if(cnt > 3) {
			heads[0] = opts[i];
			break;
		}
	}
	is_head_extra[heads[0]] = false;
	vector<bool> is_head3(V, true);
	for(int i : graph[heads[0]]) is_head3[i] = false;
	for(int i : opts) if(i != heads[0] && is_head3[i]) heads[1] = i;
	is_head_extra[heads[1]] = false;
	for(int i = 1; i < 9; i++) {
		if(heads[i] > 15 || heads[i] < 0) break;
		for(int j : graph[heads[i]]) if(is_head_extra[j]) {
			heads[i + 1] = j;
			is_head_extra[j] = false;
		}
	}
	vector<int> new_lable(V, 0);
	for(int i = 0; i < 10; i++) {
		for(int j : graph[heads[i]]) new_lable[j] += (1<<i);
	}
	vector<bool> is_special(V, false);
	for(int i : opts) is_special[i] = true;
	is_special[head] = true;
	is_special[head2] = true;
	vector<pair<int, int>> ans;
	for(int i = 0; i < U; i++) {
		if(is_special[C[i]] || is_special[D[i]]) continue;
		ans.push_back({new_lable[C[i]], new_lable[D[i]]});
	}
	InitMap(V - 12, ans.size());
	for(auto [a, b] : ans) MakeMap(a, b);
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < ans.size(); i++) MakeG(i, ans[i].first, ans[i].second);
      |                 ~~^~~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:13:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |  for(int i = 0; i < V; i++) if(graph[i].size() == V - 2) head = i;
      |                                ~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 522 ms 34896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -