Submission #315773

#	Time	Username	Problem	Language	Result	Execution time	Memory
315773		bigg	Airline Route Map (JOI18_airline)	C++14	37 / 100	526 ms	23288 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
static vector<int> grafo[MAXN], vgrafo[1505];
static int marc[1505][1505];
void Alice( int N, int M, int A[], int B[] ){
	for(int i = 0; i < M; i++) {
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}
	if(N == 1){
		InitG(1, 0);
		return;
	}
	int n = 0, m = 0;
	n++;
	n++;
	for(auto u : grafo[0]){
		if(u == 1){
			vgrafo[0].push_back(1);
			vgrafo[1].push_back(0);
			m++;
		}
	}
	for(int i = 2; i < N; i++){
		int r = n;
		int con = n + 1;
		n++;
		vgrafo[r].push_back(n);
		vgrafo[n].push_back(r);
		m++;
		n++;
		vgrafo[con].push_back(n);
		vgrafo[n].push_back(con);
		m++;
		
		n++;
		vgrafo[r].push_back(n);
		vgrafo[n].push_back(r);
		m++;
		vgrafo[con].push_back(n);
		vgrafo[n].push_back(con);
		m++;
		n++;
		vgrafo[r].push_back(n);
		vgrafo[n].push_back(r);
		m++;
		vgrafo[con].push_back(n);
		vgrafo[n].push_back(con);
		m++;
		
		
		for(auto u : grafo[i]){
			if(u == 0){
				vgrafo[n].push_back(n-1);
				vgrafo[n-1].push_back(n);
				m++;
			}
		}
		vector<int> qual;
		qual.push_back(r);
		for(int j = 1; j <= i; j++){
			n++;
			vgrafo[qual[j-1]].push_back(n);
			vgrafo[n].push_back(qual[j-1]);
			m++;
			qual.push_back(n);
		}
		for(auto u : grafo[i]){
			if(u == 0 || u > i) continue;
			
			vgrafo[qual[u]].push_back(con);
			vgrafo[con].push_back(qual[u]);
			m++;
		}
		vgrafo[qual[i]].push_back(con);
		vgrafo[con].push_back(qual[i]);
		m++;
		n++;
	}
	if(n == 0){
		InitG(1, 0);
		return;
	}
	InitG(n, m);
	int it = 0;
	for(int i = 0; i <= n; i++){
		for(auto u : vgrafo[i]){
			if(!marc[i][u]){
				MakeG(it, i, u);
				it++;
				marc[i][u] = 1;
				marc[u][i] = 1;
			}
		}	

	}

}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
static vector<int> vgrafo[1505];
static vector<pair<int, int> > grafo;
static int marc1[1505][1505], marc2[1505][1505];
static int marc[1505];
int dfs(int x, int p, int h, int con){
	int maxh = h;
	for(int i = 0; i < vgrafo[x].size(); i++){
		int viz = vgrafo[x][i];
		if(viz == p || viz == con) continue;
		maxh = max(maxh, dfs(viz, x, h + 1, con));

	}
	return maxh;
}

void Bob( int V, int U, int C[], int D[] ){
	if(V == 1){
		InitMap(1, 0);
		return;
	}
	bool okk= 0;
	if(V == 2){
		if(U != 0){
			InitMap(2, 1);
			MakeMap(1, 0);
		}
		else{
			InitMap(2,0);
		}
		return;
	}
	for(int i = 0; i < U; i++ ){
		vgrafo[C[i]].push_back(D[i]);
		vgrafo[D[i]].push_back(C[i]);
		//printf("%d %d\n", C[i], D[i]);
	}
	int n = 1, m = 0;
	for(int i = 0; i < V; i++){
		//printf("%d\n", i);
		if(vgrafo[i].size() == 1 ){
			if(vgrafo[vgrafo[i][0]].size() == 1 &&!okk){
				n = max(n, 2);
				grafo.push_back(make_pair(1, 0));
				m++;
				okk = 1;
			}
		}
		if(vgrafo[i].size() != 4) continue;
		
		int esse = 1;
		int con;
		int vizini, isconec = 0;;
		for(auto u : vgrafo[i]){
			marc[u] = 1;
			if(vgrafo[u].size() > 4) con = u;
		}
		marc[i] = 1;
		for(auto u : vgrafo[i]){
			bool ok = 0;
			for(auto v : vgrafo[u]){
				if(!marc[v]) ok = 1;
			}
			if(ok && u != con){
				vizini = u;
				break;

			}
		}
		for(auto u : vgrafo[i]){
			if(vizini == u || con == u) continue;
			if(vgrafo[u].size() == 3) isconec = 1;
		}
		esse = dfs(vizini, i, 1, con);
		n = max(esse, n);
		if(isconec){
			grafo.push_back(make_pair(esse, 0));
			//printf("GREAL %d %d\n",  esse, 0);
			m++;
		}
		if(esse == 1) continue;
		if(esse == 0){
			printf("ESSERUIM\n");
		}
		int ult = i;
		for(int j = 1; j < esse; j++){
			if(vgrafo[vizini].size() > 2){
				grafo.push_back(make_pair(esse, j));
			//printf("GREAL %d %d\n",  esse, 0);
				m++;
			}
			for(auto u : vgrafo[vizini]){
				if(vgrafo[u].size() > 1 && u != ult && u != con){
					ult = vizini;
					vizini = u;
					break;
				}
			}
		}

	}
	//printf("%d\n",m );
	InitMap(n + 1, m);
	for(int i = 0; i < m; i++){
		MakeMap(grafo[i].first, grafo[i].second);
	}

}

Compilation message (stderr)

Bob.cpp: In function 'int dfs(int, int, int, int)':
Bob.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i < vgrafo[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~
Bob.cpp: At global scope:
Bob.cpp:7:31: warning: 'marc2' defined but not used [-Wunused-variable]
    7 | static int marc1[1505][1505], marc2[1505][1505];
      |                               ^~~~~
Bob.cpp:7:12: warning: 'marc1' defined but not used [-Wunused-variable]
    7 | static int marc1[1505][1505], marc2[1505][1505];
      |            ^~~~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:77:13: warning: 'vizini' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |   esse = dfs(vizini, i, 1, con);
      |          ~~~^~~~~~~~~~~~~~~~~~~
Bob.cpp:77:13: warning: 'con' may be used uninitialized in this function [-Wmaybe-uninitialized]

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