Submission #732083

# Submission time Handle Problem Language Result Execution time Memory
732083 2023-04-28T11:07:41 Z sentheta Airline Route Map (JOI18_airline) C++17
Compilation error
0 ms 0 KB
#include "Alicelib.h"
#include <cstdio>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;


set<pii> AliceAns;
void AliceMake(int u,int v){
	AliceAns.insert(u,v);
}
void AliceFinish(int n){
	InitG(1+n+10+1, (int)AliceAns.size());
	for(auto[u,v] : AliceAns){
		MakeG(u,v);
	}
}

void Alice(int n,int m,int u[],int v[]){
	int k = 10;

	rep(i,0,m){
		u[i]++; v[i]++;
		AliceMake(u,v);
	}

	int a = 0;
	// connect 2^i to a and nodes with ith-bit ON
	rep(i,0,k){
		int vtx = n+1+i;
		AliceMake(a,vtx);

		for(int j=1; j<=n; j++) if(j&1<<i){
			AliceMake(vtx, j);
		}
	}

	// connect b to all except a and 2^0
	int b = n+11;
	for(int i=0; i<=n+10; i++) if(i!=n+1){
		AliceMake(b, i);
	}

	AliceFinish(n);
	return; InitG(3,2); MakeG(1,2); MakeG(1,3);
}

#include "Boblib.h"
#include <cstdio>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

set<pii> BobAns;
void BobMake(int u,int v){
	BobAns.insert({u,v});
}
void BobFinish(int n){
	InitMap(n, (int)BobAns.size());
	for(auto[u,v] : BobAns){
		MakeMap(u-1, v-1);
	}
}

const int N = 1069;
V<int> adj[N];
bool g[N][N];

int two[10];
int ori[N];

void Bob(int ntot,int m,int u[],int v[]){
	int k = 10, n = ntot-12;
	rep(i,0,N){
		adj[i].clear();
		rep(j,0,N) g[i][j] = 0;
	}
	rep(i,0,m){
		adj[u[i]].push_back[v[i]];
		adj[v[i]].push_back[u[i]];
		g[u[i]][v[i]] = g[v[i]][u[i]] = 1;
	}

	// find node with degree ntot-3
	int b = 0;
	while(adj[b].size()!=ntot-3) b++;

	// find two nodes disconnected from b
	V<int> a0;
	rep(i,0,ntot) if(i!=b && !g[i][b]){
		a0.push_back(i);
	}

	// determine a and 2^0
	int a=a0[0], two0=a0[1];
	bool ok = adj[a].size()==k;
	if(ok){
		V<int>&vec = adj[a];
		sort(all(vec));

		// find permutation such that it makes a line
		bool foundPerm = 0;
		do{
			bool isLine = 1;
			rep(i,1,vec.size()){
				isLine &= g[vec[i-1]][vec[i]];
			}
			if(isLine){
				foundPerm = 1;
				break;
			}
		}while(next_permutation(all(vec)));
		ok &= foundPerm;
	}
	if(!ok) swap(a, two0);
	rep(i,0,k){
		two[i] = adj[a][i];
	}

	// recover nodes
	rep(i,0,ntot){
		// check importance
		bool flag = i==a || i==b;
		rep(j,0,k) flag |= i==two[j];
		if(flag) continue;
		ori[i] = 0;

		rep(j,0,k) if(g[i][two[j]]){
			ori[i] ^= 1<<j;
		}
	}

	// recover edges
	rep(i,0,m){
		// check importance
		bool flag = 0;
		flag = u[i]==a || u[i]==b;
		rep(j,0,k) flag |= u[i]==two[j];
		flag = v[i]==a || v[i]==b;
		rep(j,0,k) flag |= v[i]==two[j];
		if(flag) continue;

		BobMake(ori[u[i]],ori[v[i]]);
	}

	BobFinish(n);
	return; InitMap(3,2); MakeMap(1,2); MakeMap(1,3);
}

Compilation message

Alice.cpp: In function 'void AliceFinish(int)':
Alice.cpp:46:12: error: too few arguments to function 'void MakeG(int, int, int)'
   46 |   MakeG(u,v);
      |            ^
In file included from Alice.cpp:1:
Alicelib.h:3:6: note: declared here
    3 | void MakeG( int pos, int C, int D );
      |      ^~~~~
Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:55:13: error: invalid conversion from 'int*' to 'int' [-fpermissive]
   55 |   AliceMake(u,v);
      |             ^
      |             |
      |             int*
Alice.cpp:40:20: note:   initializing argument 1 of 'void AliceMake(int, int)'
   40 | void AliceMake(int u,int v){
      |                ~~~~^
Alice.cpp:55:15: error: invalid conversion from 'int*' to 'int' [-fpermissive]
   55 |   AliceMake(u,v);
      |               ^
      |               |
      |               int*
Alice.cpp:40:26: note:   initializing argument 2 of 'void AliceMake(int, int)'
   40 | void AliceMake(int u,int v){
      |                      ~~~~^
Alice.cpp:76:31: error: too few arguments to function 'void MakeG(int, int, int)'
   76 |  return; InitG(3,2); MakeG(1,2); MakeG(1,3);
      |                               ^
In file included from Alice.cpp:1:
Alicelib.h:3:6: note: declared here
    3 | void MakeG( int pos, int C, int D );
      |      ^~~~~
Alice.cpp:76:43: error: too few arguments to function 'void MakeG(int, int, int)'
   76 |  return; InitG(3,2); MakeG(1,2); MakeG(1,3);
      |                                           ^
In file included from Alice.cpp:1:
Alicelib.h:3:6: note: declared here
    3 | void MakeG( int pos, int C, int D );
      |      ^~~~~
In file included from /usr/include/c++/10/set:61,
                 from Alice.cpp:17:
/usr/include/c++/10/bits/stl_set.h: In instantiation of 'void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]':
Alice.cpp:41:21:   required from here
/usr/include/c++/10/bits/stl_set.h:567:31: error: no matching function for call to 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_insert_range_unique(int&, int&)'
  567 |  { _M_t._M_insert_range_unique(__first, __last); }
      |    ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/map:60,
                 from Alice.cpp:16:
/usr/include/c++/10/bits/stl_tree.h:1105:2: note: candidate: 'template<class _InputIterator> std::__enable_if_t<std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_unique(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
 1105 |  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1105:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<std::is_same<std::pair<int, int>, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value, void> std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_insert_range_unique<_InputIterator>(_InputIterator, _InputIterator) [with _InputIterator = int]':
/usr/include/c++/10/bits/stl_set.h:567:31:   required from 'void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
Alice.cpp:41:21:   required from here
/usr/include/c++/10/bits/stl_tree.h:1105:2: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
/usr/include/c++/10/bits/stl_set.h: In instantiation of 'void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]':
Alice.cpp:41:21:   required from here
/usr/include/c++/10/bits/stl_tree.h:1114:2: note: candidate: 'template<class _InputIterator> std::__enable_if_t<(! std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value)> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_unique(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
 1114 |  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1114:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<(! std::is_same<std::pair<int, int>, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value), void> std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_insert_range_unique<_InputIterator>(_InputIterator, _InputIterator) [with _InputIterator = int]':
/usr/include/c++/10/bits/stl_set.h:567:31:   required from 'void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
Alice.cpp:41:21:   required from here
/usr/include/c++/10/bits/stl_tree.h:1113:52: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
 1113 |  __enable_if_t<!__same_value_type<_InputIterator>::value>
      |                                                    ^~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:63:22: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   63 |   adj[u[i]].push_back[v[i]];
      |                      ^
Bob.cpp:64:22: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   64 |   adj[v[i]].push_back[u[i]];
      |                      ^
Bob.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |  while(adj[b].size()!=ntot-3) b++;
      |        ~~~~~~~~~~~~~^~~~~~~~
Bob.cpp:80:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |  bool ok = adj[a].size()==k;
      |            ~~~~~~~~~~~~~^~~