oj.uz

Submission #469447

# Submission time Handle Problem Language Result Execution time Memory
469447 2021-09-01T02:35:59 Z errorgorn Airline Route Map (JOI18_airline) C++17
0 / 100
 624 ms 33904 KB 
#include "Alicelib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bugz

void Alice( int n, int m, int a[], int b[] ){
	int arr[10][10]={
		{0,0,0,0,0,0,0,0,1,0},	
		{0,0,1,0,0,0,1,0,0,0},	
		{0,0,0,1,0,0,0,0,0,0},	
		{0,0,0,0,1,1,0,0,0,0},	
		{0,0,0,0,0,1,0,0,0,0},	
		{0,0,0,0,0,0,0,1,0,0},	
		{0,0,0,0,0,0,0,1,1,1},	
		{0,0,0,0,0,0,0,0,1,1},	
		{0,0,0,0,0,0,0,0,0,1},	
		{0,0,0,0,0,0,0,0,0,0}	
	};
	
	vector<ii> v;
	
	rep(x,0,10) rep(y,0,10) if (arr[x][y]) v.pub({n+x,n+y});
	
	rep(x,0,n+10) v.pub({n+10,x});
	rep(x,0,n) v.pub({n+11,x});
	
	rep(x,0,m) v.pub({a[x],b[x]});
	
	rep(x,0,n){
		rep(y,0,10) if (x&(1<<y)) v.pub({x,n+y});
	}
	
	InitG(n+12,sz(v));
	rep(x,0,sz(v)) MakeG(x,v[x].fi,v[x].se);
}


#include "Boblib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

bool grid[1030][1030];
int ord[1005];

void Bob( int n, int m, int c[], int d[] ){
	int arr[10][10]={
		{0,0,0,0,0,0,0,0,1,0},	
		{0,0,1,0,0,0,1,0,0,0},	
		{0,0,0,1,0,0,0,0,0,0},	
		{0,0,0,0,1,1,0,0,0,0},	
		{0,0,0,0,0,1,0,0,0,0},	
		{0,0,0,0,0,0,0,1,0,0},	
		{0,0,0,0,0,0,0,1,1,1},	
		{0,0,0,0,0,0,0,0,1,1},	
		{0,0,0,0,0,0,0,0,0,1},	
		{0,0,0,0,0,0,0,0,0,0}	
	};
	
	rep(x,0,m){
		grid[c[x]][d[x]]=true;
		grid[d[x]][c[x]]=true;
	}
		
	int idx=-1;
	int mx=0;
	
	rep(x,0,n){
		int deg=0;
		rep(y,0,n) if (grid[x][y]) deg++;
		
		if (deg>mx){
			mx=deg;
			idx=x;
		}
	}
	
	//cout<<mx<<" "<<idx<<endl;	
	int idx2;
	rep(x,0,n) if (x!=idx && !grid[idx][x]) idx2=x;
	cout<<idx2<<endl;
	
	vector<int> ids;
	rep(x,0,n) if (x!=idx2 && x!=idx && !grid[idx2][x]) ids.pub(x);
	
	sort(all(ids));
	//for (auto &it:ids) cout<<it<<" "; cout<<endl;
	
	do{
		bool can=true;
		rep(x,0,10) rep(y,x+1,10){
			if (arr[x][y]!=grid[ids[x]][ids[y]]){
				can=false;
				goto end;
			}	
		}
		
		end:;
		
		if (can) break;
	} while (next_permutation(all(ids)));
	
	//for (auto &it:ids) cout<<it<<" "; cout<<endl;
	
	rep(x,0,n) if (x!=idx && x!=idx2){
		bool can=true;
		rep(y,0,sz(ids)) if (x==ids[y]) can=false;
		if (can){
			int num=0;
			rep(y,0,10) if (grid[x][ids[y]]) num|=(1<<y);
			
			ord[num]=x;		
		}
	}
	
	vector<ii> ans;
	rep(x,0,n-12) rep(y,x+1,n-12){
		if (grid[ord[x]][ord[y]]) ans.pub({x,y});
	}
	
	InitMap(n-12,sz(ans));
	for (auto &it:ans) MakeMap(it.fi,it.se);
	
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:14:14: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 | #define endl '\n'
      |              ^~~~
Bob.cpp:67:6: note: 'idx2' was declared here
   67 |  int idx2;
      |      ^~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 4588 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 4588 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 624 ms 33904 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -