Submission #315758

#	Time	Username	Problem	Language	Result	Execution time	Memory
315758		bigg	Airline Route Map (JOI18_airline)	C++14	0 / 100	468 ms	23136 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]);
	}
	int n = 0, m = 0;
	for(int i = 1; i < N; i++){
		int r = n;
		n++;
		vgrafo[r].push_back(n);
		vgrafo[n].push_back(r);
		m++;
		n++;
		vgrafo[r].push_back(n);
		vgrafo[n].push_back(r);
		m++;
		n++;
		vgrafo[r].push_back(n);
		vgrafo[n].push_back(r);
		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;
			n++;
			vgrafo[qual[u]].push_back(n);
			vgrafo[n].push_back(qual[u]);
			m++;
		}
		n++;
	}
	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> grafo[MAXN], vgrafo[1505];
static int marc1[1505][1505], marc2[1505][1505];
static int marc[1505];
int dfs(int x, int p, int h){
	int maxh = h;
	for(int i = 0; i < vgrafo[x].size(); i++){
		int viz = vgrafo[x][i];
		if(viz == p) continue;
		maxh = max(maxh, dfs(viz, x, h + 1));

	}
	return maxh;
}

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

	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() <= 3) continue;
		n++;
		int esse = 1;
		int vizini, isconec = 0;;
		for(auto u : vgrafo[i]){
			marc[u] = 1;
		}
		for(auto u : vgrafo[i]){
			bool ok = 1;
			for(auto v : vgrafo[u]){
				if(marc[v]) ok = 0, isconec = 1;
			}
			if(!ok || vgrafo[u].size() == 1) continue;
			esse = dfs(u, i, 1);
			vizini = u;
		}
		if(isconec){
			grafo[esse].push_back(0);
			grafo[0].push_back(esse);
			m++;
		}
		if(esse == 1) continue;
		int ult = i;
		for(int j = 1; j < esse; j++){
			if(vgrafo[vizini].size() > 2){
				grafo[esse].push_back(j);
				grafo[j].push_back(esse);
		//		printf("GREAL %d %d %d %d\n", i, vizini, esse, j);
				m++;
			}
			for(auto u : vgrafo[vizini]){
				if(vgrafo[u].size() > 1 && u != ult){
					ult = vizini;
					vizini = u;
					break;
				}
			}
		}

	}
	//printf("%d\n",m );
	InitMap(n, m);
	for(int i = 1; i < n; i++){
		for(auto u : grafo[i]){
			if(marc1[i][u]) continue;
			MakeMap(i, u);
			marc1[i][u] = 1;
			marc1[u][i] = 1;
		}
	}

}

Compilation message (stderr)

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

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