oj.uz

Submission #315758

# Submission time Handle Problem Language Result Execution time Memory
315758 2020-10-23T21:23:07 Z bigg Airline Route Map (JOI18_airline) C++14
0 / 100
 468 ms 23136 KB 
#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;
			}
		}	

	}

}


#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7936 KB Output is correct
2 Correct 7 ms 7680 KB Output is correct
3 Correct 7 ms 7680 KB Output is correct
4 Correct 7 ms 7680 KB Output is correct
5 Correct 7 ms 7680 KB Output is correct
6 Correct 7 ms 7680 KB Output is correct
7 Correct 7 ms 7936 KB Output is correct
8 Correct 7 ms 8192 KB Output is correct
9 Correct 7 ms 7680 KB Output is correct
10 Correct 7 ms 7680 KB Output is correct
11 Correct 7 ms 7680 KB Output is correct
12 Correct 7 ms 7680 KB Output is correct
13 Correct 7 ms 7936 KB Output is correct
14 Correct 7 ms 7936 KB Output is correct
15 Correct 7 ms 7680 KB Output is correct
16 Correct 7 ms 7680 KB Output is correct
17 Correct 7 ms 7680 KB Output is correct
18 Correct 7 ms 7680 KB Output is correct
19 Correct 7 ms 7680 KB Output is correct
20 Correct 7 ms 7936 KB Output is correct
21 Correct 8 ms 7680 KB Output is correct
22 Correct 7 ms 7424 KB Output is correct
23 Correct 7 ms 7680 KB Output is correct
24 Correct 7 ms 7168 KB Output is correct
25 Correct 7 ms 7168 KB Output is correct
26 Correct 7 ms 7168 KB Output is correct
27 Correct 7 ms 7424 KB Output is correct
28 Correct 8 ms 7680 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 7 ms 7680 KB Output is correct
32 Correct 7 ms 7680 KB Output is correct
33 Correct 7 ms 7680 KB Output is correct
34 Correct 7 ms 7680 KB Output is correct
35 Correct 7 ms 7680 KB Output is correct
36 Correct 7 ms 7936 KB Output is correct
37 Correct 7 ms 7936 KB Output is correct
38 Correct 7 ms 7936 KB Output is correct
39 Correct 7 ms 7936 KB Output is correct
40 Correct 8 ms 7936 KB Output is correct
41 Correct 7 ms 7680 KB Output is correct
42 Correct 7 ms 7680 KB Output is correct
43 Correct 7 ms 7680 KB Output is correct
44 Correct 7 ms 7680 KB Output is correct
45 Correct 7 ms 7680 KB Output is correct
46 Correct 7 ms 7680 KB Output is correct
47 Correct 7 ms 7680 KB Output is correct
48 Correct 7 ms 7680 KB Output is correct
49 Correct 7 ms 7680 KB Output is correct
50 Correct 7 ms 7680 KB Output is correct
51 Incorrect 5 ms 3456 KB Wrong Answer [1]
52 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7936 KB Output is correct
2 Correct 7 ms 7680 KB Output is correct
3 Correct 7 ms 7680 KB Output is correct
4 Correct 7 ms 7680 KB Output is correct
5 Correct 7 ms 7680 KB Output is correct
6 Correct 7 ms 7680 KB Output is correct
7 Correct 7 ms 7936 KB Output is correct
8 Correct 7 ms 8192 KB Output is correct
9 Correct 7 ms 7680 KB Output is correct
10 Correct 7 ms 7680 KB Output is correct
11 Correct 7 ms 7680 KB Output is correct
12 Correct 7 ms 7680 KB Output is correct
13 Correct 7 ms 7936 KB Output is correct
14 Correct 7 ms 7936 KB Output is correct
15 Correct 7 ms 7680 KB Output is correct
16 Correct 7 ms 7680 KB Output is correct
17 Correct 7 ms 7680 KB Output is correct
18 Correct 7 ms 7680 KB Output is correct
19 Correct 7 ms 7680 KB Output is correct
20 Correct 7 ms 7936 KB Output is correct
21 Correct 8 ms 7680 KB Output is correct
22 Correct 7 ms 7424 KB Output is correct
23 Correct 7 ms 7680 KB Output is correct
24 Correct 7 ms 7168 KB Output is correct
25 Correct 7 ms 7168 KB Output is correct
26 Correct 7 ms 7168 KB Output is correct
27 Correct 7 ms 7424 KB Output is correct
28 Correct 8 ms 7680 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 7 ms 7680 KB Output is correct
32 Correct 7 ms 7680 KB Output is correct
33 Correct 7 ms 7680 KB Output is correct
34 Correct 7 ms 7680 KB Output is correct
35 Correct 7 ms 7680 KB Output is correct
36 Correct 7 ms 7936 KB Output is correct
37 Correct 7 ms 7936 KB Output is correct
38 Correct 7 ms 7936 KB Output is correct
39 Correct 7 ms 7936 KB Output is correct
40 Correct 8 ms 7936 KB Output is correct
41 Correct 7 ms 7680 KB Output is correct
42 Correct 7 ms 7680 KB Output is correct
43 Correct 7 ms 7680 KB Output is correct
44 Correct 7 ms 7680 KB Output is correct
45 Correct 7 ms 7680 KB Output is correct
46 Correct 7 ms 7680 KB Output is correct
47 Correct 7 ms 7680 KB Output is correct
48 Correct 7 ms 7680 KB Output is correct
49 Correct 7 ms 7680 KB Output is correct
50 Correct 7 ms 7680 KB Output is correct
51 Incorrect 5 ms 3456 KB Wrong Answer [1]
52 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 468 ms 23136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -