oj.uz

Submission #988153

# Submission time Handle Problem Language Result Execution time Memory
988153 2024-05-24T07:00:22 Z boyliguanhan Airline Route Map (JOI18_airline) C++17
0 / 100
 631 ms 39992 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
	vector<pair<int,int>>EEE;
	for(int i=0;i<M;i++)
		EEE.push_back({A[i],B[i]});
	EEE.push_back({N,N+1});
	for(int i=0;i<10;i++)
		EEE.push_back({N+1,N+i+2});
	for(int i=0;i<9;i++)
		EEE.push_back({N+2+i,N+3+i});
	EEE.push_back({N+8,N+11});
	EEE.push_back({N+8,N+10});
	EEE.push_back({N+7,N+9});
	int cnt=0;
	for(int i=3;cnt<N;i++){
		if(__builtin_popcount(i)>1){
			for(int j=0;j<10;j++) if(i&1<<j)
				EEE.push_back({cnt,N+2+j});
			cnt++;
		}
	}
	InitG(N+12,EEE.size());
	for(int i=0;i<EEE.size();i++)
		MakeG(i,EEE[i].first,EEE[i].second);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define CTD(D,I) for(auto i:adj[z]) if(IN[i]&&i-w&&DEG[i]==D&&i!=v[I]){w=z,v.push_back(z=i);break;}
vector<int>adj[1012];
int means[1024],val[1012],DEG[1012],IN[1012];
void Bob( int V, int U, int C[], int D[] ){
	int CC=0;
	for(int i=3;i<1024;i++)
		if(__builtin_popcount(i)>1)
			means[i]=CC++;
	for(int i=0;i<U;i++)
		adj[C[i]].push_back(D[i]),
		adj[D[i]].push_back(C[i]);
	int x,y,z,w;
	for(int i=0;i<V;i++)
		if(adj[i].size()<2)
			x=i;
	y=adj[x][0];
	for(auto j:adj[y])
		IN[j]=1;
	for(int i=0;i<V;i++)
		for(auto j:adj[i])
			DEG[i]+=IN[j];
	for(auto i:adj[y])
		if(DEG[i]==1)
			z=i;
	vector<int>v{z};
	for(int Q=5;Q--;)for(auto i:adj[z])
		if(IN[i]&&i-w){w=z,v.push_back(z=i);break;}
	for(auto i:adj[z]) CTD(4,0)
	for(auto i:adj[z]) for(auto i:adj[z])
		if(IN[i]&&i-w&&DEG[i]==3&&count(adj[i].begin(),adj[i].end(),v[5])){
			w=z,v.push_back(z=i);break;}
	for(auto i:adj[z]) CTD(3,5)
	for(auto i:adj[z]) CTD(2,0)
	for(int i=0;i<10;i++)
		for(auto j:adj[v[i]])
			val[j]+=1<<i;
	vector<pair<int,int>>EEE;
	for(int i=0;i<U;i++) if(!IN[C[i]]&&!IN[D[i]]) {
		int A=means[val[C[i]]],B=means[val[D[i]]];
		EEE.push_back({A,B});
	}
	swap(EEE.back(),EEE[0]);
	InitMap(V-12,EEE.size());
	for(auto[i,j]:EEE)
		MakeMap(i,j);
}

Compilation message

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:31:11: warning: unused variable 'i' [-Wunused-variable]
   31 |  for(auto i:adj[z]) CTD(4,0)
      |           ^
Bob.cpp:32:11: warning: unused variable 'i' [-Wunused-variable]
   32 |  for(auto i:adj[z]) for(auto i:adj[z])
      |           ^
Bob.cpp:35:11: warning: unused variable 'i' [-Wunused-variable]
   35 |  for(auto i:adj[z]) CTD(3,5)
      |           ^
Bob.cpp:36:11: warning: unused variable 'i' [-Wunused-variable]
   36 |  for(auto i:adj[z]) CTD(2,0)
      |           ^
Bob.cpp:30:11: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |   if(IN[i]&&i-w){w=z,v.push_back(z=i);break;}
      |      ~~~~~^~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15616 KB Output is correct
2 Correct 4 ms 15628 KB Output is correct
3 Correct 3 ms 15620 KB Output is correct
4 Runtime error 7 ms 18176 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15616 KB Output is correct
2 Correct 4 ms 15628 KB Output is correct
3 Correct 3 ms 15620 KB Output is correct
4 Runtime error 7 ms 18176 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 39992 KB Output is correct : V - N = 12
2 Correct 265 ms 37164 KB Output is correct : V - N = 12
3 Correct 130 ms 21420 KB Output is correct : V - N = 12
4 Correct 8 ms 15948 KB Output is correct : V - N = 12
5 Correct 132 ms 18384 KB Output is correct : V - N = 12
6 Correct 247 ms 36112 KB Output is correct : V - N = 12
7 Correct 497 ms 38140 KB Output is correct : V - N = 12
8 Correct 521 ms 39272 KB Output is correct : V - N = 12
9 Correct 206 ms 21936 KB Output is correct : V - N = 12
10 Correct 31 ms 16848 KB Output is correct : V - N = 12
11 Correct 35 ms 17088 KB Output is correct : V - N = 12
12 Correct 312 ms 27456 KB Output is correct : V - N = 12
13 Correct 377 ms 38308 KB Output is correct : V - N = 12
14 Correct 475 ms 39012 KB Output is correct : V - N = 12
15 Correct 373 ms 33264 KB Output is correct : V - N = 12
16 Correct 54 ms 17700 KB Output is correct : V - N = 12
17 Correct 13 ms 16796 KB Output is correct : V - N = 12
18 Correct 221 ms 21892 KB Output is correct : V - N = 12
19 Correct 341 ms 39116 KB Output is correct : V - N = 12
20 Correct 631 ms 37984 KB Output is correct : V - N = 12
21 Correct 114 ms 19884 KB Output is correct : V - N = 12
22 Correct 99 ms 18644 KB Output is correct : V - N = 12
23 Correct 51 ms 17120 KB Output is correct : V - N = 12
24 Correct 5 ms 15564 KB Output is correct : V - N = 12
25 Correct 18 ms 16720 KB Output is correct : V - N = 12
26 Correct 106 ms 18828 KB Output is correct : V - N = 12
27 Correct 173 ms 19312 KB Output is correct : V - N = 12
28 Correct 91 ms 18952 KB Output is correct : V - N = 12
29 Correct 69 ms 17240 KB Output is correct : V - N = 12
30 Correct 7 ms 16124 KB Output is correct : V - N = 12
31 Runtime error 11 ms 18172 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -