Submission #414924

#	Time	Username	Problem	Language	Result	Execution time	Memory
414924		Pro_ktmr	Airline Route Map (JOI18_airline)	C++17	100 / 100	849 ms	29304 KiB

Alice

#include"bits/stdc++.h"
#include"Alicelib.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };
 
// void InitG(int V, int U)
// void MakeG(int pos, int C, int D)
 
void Alice(int N, int M, int A[], int B[]){
	vector<pair<int,int>> ret;
	rep(i, M) ret.pb({ A[i], B[i] });
 
	rep(i, N){
		rep(j, 10){
			if((i>>j)&1) ret.pb({i, N+j});
		}
	}
	rep(i, 10) ret.pb({ N+10, N+i });
	rep(i, 9) ret.pb({ N+i, N+1+i });
	rep(i, N+10){
		if(N > 500 && i == N) continue;
		if(N <= 500 && i == N+9) continue;
		ret.pb({ i, N+11 });
	}
 
	InitG(N+12, ret.size());
	rep(i, ret.size()) MakeG(i, ret[i].first, ret[i].second);
}

Bob

#include"bits/stdc++.h"
#include"Boblib.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };
 
// void InitMap(int N, int M)
// void MakeMap(int A, int B)
 
bool isExist(vector<int>& v, int n){
	rep(i, v.size()){
		if(v[i] == n) return true;
	}
	return false;
}
 
void Bob(int V, int U, int C[], int D[]){
	if(V == 13){
		InitMap(1, 0);
		return;
	}
 
	vector<int> e[1020];
	rep(i, U){
		e[C[i]].pb(D[i]);
		e[D[i]].pb(C[i]);
		//cout << C[i] << " " << D[i] << endl;
	}
 
	int N = V-12;
	int r, b;
	vector<int> t(10, -1);
	rep(i, V){
		if(e[i].size() == N+9){
			r = i;
			rep(j, V){
				if(j != r && !isExist(e[r], j) && e[j].size() == 10) b = j;
				else if(j != r && !isExist(e[r], j)) t[0] = j;
			}
			int c = 0;
			rep(j, 10){
				if(isExist(e[t[0]], e[b][j])) c++;
			}
			if(c == 1 && e[t[0]].size()-2 == N/2) break;
		}
	}
	
	rep(i, 9){
		rep(j, 10){
			//cout << e[b][j] << " " << isExist(e[t[i]], e[b][j]) << " " << !isExist(t, e[b][j]) << endl;
			if(isExist(e[t[i]], e[b][j]) && !isExist(t, e[b][j])){
				t[i+1] = e[b][j];
			}
		}
	}
	if(N <= 500) reverse(all(t));
	//cout << "rb: " << r << " " << b << endl;
	//rep(i, 10) cout << t[i] << " ";
	//cout << endl;
 
	vector<int> ans(V, 0);
	rep(i, 10){
		rep(j, e[t[i]].size()){
			ans[e[t[i]][j]] += 1<<i;
		}
	}
 
	t.pb(r);
	t.pb(b);
	vector<pair<int, int>> edges;
	rep(i, U){
		if(isExist(t, C[i]) || isExist(t, D[i])) continue;
		edges.pb({ ans[C[i]], ans[D[i]] });
		//cout << ans[C[i]] << " " << ans[D[i]] << endl;
	}
 
	InitMap(N, edges.size());
	rep(i, edges.size()) MakeMap(edges[i].first, edges[i].second);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:21:2: note: in expansion of macro 'rep'
   21 |  rep(i, M) ret.pb({ A[i], B[i] });
      |  ^~~
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:23:2: note: in expansion of macro 'rep'
   23 |  rep(i, N){
      |  ^~~
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:24:3: note: in expansion of macro 'rep'
   24 |   rep(j, 10){
      |   ^~~
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:28:2: note: in expansion of macro 'rep'
   28 |  rep(i, 10) ret.pb({ N+10, N+i });
      |  ^~~
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:29:2: note: in expansion of macro 'rep'
   29 |  rep(i, 9) ret.pb({ N+i, N+1+i });
      |  ^~~
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:30:2: note: in expansion of macro 'rep'
   30 |  rep(i, N+10){
      |  ^~~
Alice.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Alice.cpp:37:2: note: in expansion of macro 'rep'
   37 |  rep(i, ret.size()) MakeG(i, ret[i].first, ret[i].second);
      |  ^~~

Bob.cpp: In function 'bool isExist(std::vector<int>&, int)':
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:20:2: note: in expansion of macro 'rep'
   20 |  rep(i, v.size()){
      |  ^~~
Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:33:2: note: in expansion of macro 'rep'
   33 |  rep(i, U){
      |  ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:42:2: note: in expansion of macro 'rep'
   42 |  rep(i, V){
      |  ^~~
Bob.cpp:43:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |   if(e[i].size() == N+9){
      |      ~~~~~~~~~~~~^~~~~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:45:4: note: in expansion of macro 'rep'
   45 |    rep(j, V){
      |    ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:50:4: note: in expansion of macro 'rep'
   50 |    rep(j, 10){
      |    ^~~
Bob.cpp:53:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |    if(c == 1 && e[t[0]].size()-2 == N/2) break;
      |                 ~~~~~~~~~~~~~~~~~^~~~~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:57:2: note: in expansion of macro 'rep'
   57 |  rep(i, 9){
      |  ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:58:3: note: in expansion of macro 'rep'
   58 |   rep(j, 10){
      |   ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:71:2: note: in expansion of macro 'rep'
   71 |  rep(i, 10){
      |  ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:72:3: note: in expansion of macro 'rep'
   72 |   rep(j, e[t[i]].size()){
      |   ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:80:2: note: in expansion of macro 'rep'
   80 |  rep(i, U){
      |  ^~~
Bob.cpp:12:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   12 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Bob.cpp:87:2: note: in expansion of macro 'rep'
   87 |  rep(i, edges.size()) MakeMap(edges[i].first, edges[i].second);
      |  ^~~

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