Submission #622871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
622871	2022-08-04T17:23:41 Z	CSQ31	Airline Route Map (JOI18_airline)	C++17	Compilation error	0 ms	0 KB

Alice

#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define pb push_back
void Alice( int n, int m, int A[], int B[] ){
	vector<array<int,2>>edge;
	for(int i=0;i<m;i++){
		edge.push_back({A[i],B[i]});
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<10;j++){
			if(i&(1<<j)){
				edge.push_back({i,j+n});
			}
		}
	}
	for(int j=0;j+1<10;j++)edge.push_back({j+n,j+n+1});
	for(int j=0;j<10;j++){
	    edge.push_back({n+10,j+n});
		edge.push_back({n+11,j+n});
	}
	InitG(n+12,sz(edge));
	//cout<<vert<<" "<<M<<'\n';
	int pos = 0;
	for(auto x:edge)MakeG(pos++,x[0],x[1]);
}
bool vis[222222],mark[22222];
int lab[22222];
void Bob( int V, int U, int C[], int D[]){
	//for(int i=0;i<U;i++)cout<<C[i]<<" "<<D[i]<<'\n';
	vector<vector<int>>adj(V);
	for(int i=0;i<U;i++){
		adj[C[i]].pb(D[i]);
		adj[D[i]].pb(C[i]);
	}
	for(int i=0;i<V;i++){
		sort(adj[i].begin(),adj[i].end());
	}
	int n0 = 0,n1 = 0;
	for(int i=0;i<V;i++){
		for(int j=i+1;j<V;j++){
			if(sz(adj[i]) != 10 || sz(adj[j])!=10)continue;
			if(adj[i] == adj[j]){
				n0 = i;
				n1 = j;
				break;
			}
		}
	} //the ten bits
	//cout<<"TES"<<'\n';
	//cout<<n0<<" "<<n1<<'\n';
	vector<int>bit;
	for(int x:adj[n0]){
		bit.pb(x);
		mark[x] = 1;
	}
	int root = 0;
	for(int i=0;i<10;i++){ //find a enpoint
		int deg = 0;
		for(int x:adj[bit[i]])deg+=mark[x];
		if(deg==1)root = bit[i];
	}
	queue<int>q;
	q.push(root);
	vis[root] = 1;
	vector<int>ord;
	while(!q.empty()){
		int v = q.front();
		ord.pb(v);
		q.pop();
		for(int x:adj[v]){
			if(!vis[x] && mark[x]){
				vis[x] = 1;
				q.push(x);
			}
		}
	}
	//for(int x:ord)cout<<x<<" ";
	//cout<<'\n';
	if(sz(adj[ord[0]]) < sz(adj[ord[9]]))reverse(ord.begin(),ord.end());
	//wrong order
	for(int i=0;i<V;i++){
		if(mark[i] || i==n0 || i==n1)continue;
		for(int x:adj[i]){
			if(mark[x]){
				for(int j=0;j<10;j++){
					if(ord[j] ==x)lab[i]+=(1<<j);
				}
			}
			
		}
	}
	vector<array<int,2>>edge;
	for(int i=0;i<V;i++){
		if(mark[i] || i==n0 || i==n1)continue;
		for(int x:adj[i]){
			if(mark[x] || x==n0 || x==n1)continue;
			if(x > i)edge.pb({lab[i],lab[x]});
		}
	}
	InitMap(V-12,sz(edge));
	for(auto x:edge){
		//MakeMap(x[0],x[1]);
		//cout<<x[0]<<" "<<x[1]<<'\n';
	}
	for(auto x:edge){
		MakeMap(x[0],x[1]);
		//cout<<x[0]<<" "<<x[1]<<'\n';
	}
}

Bob

//#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
bool vis[222222],mark[22222];
int lab[22222];
void Bob( int V, int U, int C[], int D[]){
	//for(int i=0;i<U;i++)cout<<C[i]<<" "<<D[i]<<'\n';
	vector<vector<int>>adj(V);
	for(int i=0;i<U;i++){
		adj[C[i]].pb(D[i]);
		adj[D[i]].pb(C[i]);
	}
	for(int i=0;i<V;i++){
		sort(adj[i].begin(),adj[i].end());
	}
	int n0 = 0,n1 = 0;
	for(int i=0;i<V;i++){
		for(int j=i+1;j<V;j++){
			if(sz(adj[i]) != 10 || sz(adj[j])!=10)continue;
			if(adj[i] == adj[j]){
				n0 = i;
				n1 = j;
				break;
			}
		}
	} //the ten bits
	//cout<<"TES"<<'\n';
	//cout<<n0<<" "<<n1<<'\n';
	vector<int>bit;
	for(int x:adj[n0]){
		bit.pb(x);
		mark[x] = 1;
	}
	int root = 0;
	for(int i=0;i<10;i++){ //find a enpoint
		int deg = 0;
		for(int x:adj[bit[i]])deg+=mark[x];
		if(deg==1)root = bit[i];
	}
	queue<int>q;
	q.push(root);
	vis[root] = 1;
	vector<int>ord;
	while(!q.empty()){
		int v = q.front();
		ord.pb(v);
		q.pop();
		for(int x:adj[v]){
			if(!vis[x] && mark[x]){
				vis[x] = 1;
				q.push(x);
			}
		}
	}
	//for(int x:ord)cout<<x<<" ";
	//cout<<'\n';
	if(sz(adj[ord[0]]) < sz(adj[ord[9]]))reverse(ord.begin(),ord.end());
	//wrong order
	for(int i=0;i<V;i++){
		if(mark[i] || i==n0 || i==n1)continue;
		for(int x:adj[i]){
			if(mark[x]){
				for(int j=0;j<10;j++){
					if(ord[j] ==x)lab[i]+=(1<<j);
				}
			}
			
		}
	}
	vector<array<int,2>>edge;
	for(int i=0;i<V;i++){
		if(mark[i] || i==n0 || i==n1)continue;
		for(int x:adj[i]){
			if(mark[x] || x==n0 || x==n1)continue;
			if(x > i)edge.pb({lab[i],lab[x]});
		}
	}
	InitMap(V-12,sz(edge));
	for(auto x:edge){
		//MakeMap(x[0],x[1]);
		//cout<<x[0]<<" "<<x[1]<<'\n';
	}
	for(auto x:edge){
		MakeMap(x[0],x[1]);
		//cout<<x[0]<<" "<<x[1]<<'\n';
	}
}

Compilation message

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:25:2: error: 'InitG' was not declared in this scope
   25 |  InitG(n+12,sz(edge));
      |  ^~~~~
Alice.cpp:28:18: error: 'MakeG' was not declared in this scope
   28 |  for(auto x:edge)MakeG(pos++,x[0],x[1]);
      |                  ^~~~~
Alice.cpp: In function 'void Bob(int, int, int*, int*)':
Alice.cpp:104:2: error: 'InitMap' was not declared in this scope
  104 |  InitMap(V-12,sz(edge));
      |  ^~~~~~~
Alice.cpp:110:3: error: 'MakeMap' was not declared in this scope
  110 |   MakeMap(x[0],x[1]);
      |   ^~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:22:7: error: 'sz' was not declared in this scope
   22 |    if(sz(adj[i]) != 10 || sz(adj[j])!=10)continue;
      |       ^~
Bob.cpp:60:5: error: 'sz' was not declared in this scope
   60 |  if(sz(adj[ord[0]]) < sz(adj[ord[9]]))reverse(ord.begin(),ord.end());
      |     ^~
Bob.cpp:81:15: error: 'sz' was not declared in this scope
   81 |  InitMap(V-12,sz(edge));
      |               ^~
Bob.cpp:81:2: error: 'InitMap' was not declared in this scope
   81 |  InitMap(V-12,sz(edge));
      |  ^~~~~~~
Bob.cpp:87:3: error: 'MakeMap' was not declared in this scope
   87 |   MakeMap(x[0],x[1]);
      |   ^~~~~~~