oj.uz

Submission #236195

# Submission time Handle Problem Language Result Execution time Memory
236195 2020-05-31T13:32:24 Z Knps4422 Airline Route Map (JOI18_airline) C++14
0 / 100
 754 ms 30872 KB 
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include"Alicelib.h"
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef complex<int> point;
const int nmax = 3005;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = INT_MAX;

void Alice( int n , int m , int a[] , int b[]){
	vec < pii > edges;
	for(int i = 0; i < m ;i++){
		edges.pb({a[i], b[i]});
	}
	for(int i = 0 ; i < n ;i++){
		edges.pb({i,n});
		for(int k = 0 ; k < 10 ; k++){
			if(i&(1<<k))edges.pb({i,n+k+1});
		}
	}
	for(int i = n+1; i <= n+10; i++){
		edges.pb({i,n});
		edges.pb({i,n+11});
	}
	for(int i = n+1; i < n+10 ; i++){
		edges.pb({i,i+1});
	}
	int pos = 0;
	InitG( n + 12 , edges.size());
	for( pii asd : edges){
		MakeG(pos++, asd.fr, asd.sc);
	}
}

/*int main(){
	fast;

}*/
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include"Boblib.h"
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(int x = 1 ; x <= (int)y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef complex<int> point;
const int nmax = 1500;
const ll linf = 1e18;
const ll mod = 998244353;
const int inf = INT_MAX;

void Bob( int n , int m , int a[] , int b[]){
	vec < int > g[nmax];
	for(int i = 0 ; i < m ; i++){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	int A = 0;
	set < int > aux;
	for(int i = 1 ; i < n ; i++){
		if(g[i].size() > g[A].size()) A = i;
	}
	aux.insert(A);
	set<int> c;
	for(int j : g[A]){
		c.insert(j);
	}
	int B = 0;
	for(int i = 0 ; i < n ; i++){
		if(!c.count(i) && i != A)B = i; 
	}
	aux.insert(B);
	set < int > bits, bits_used;
	for(int j : g[B]){
		bits.insert(j);
		aux.insert(j);
	}
	int start;
	for(int i : bits){
		int cnt = 0;
		for(int j : g[i]){
			cnt += bits.count(j);
		}
		if( cnt == 1 ) start = i;
	}
	vec < int > bito;
	bito.pb(start);
	bits_used.insert(start);
	int p = start, nxp = -1;
	for(int ii = 1; ii < 10 ; ii++){
		for(int j : g[p]){
			if( bits_used.count(j) == 0 && bits.count(j) > 0 ){
				nxp = j;
				bito.pb(j);
			}	
		}
		p = nxp;
		bits_used.insert(p);
	}
	if(g[bito[0]].size() < g[bito[9]].size())reverse(bito.begin(),bito.end());
	int mask[nmax];
	for(int i = 0; i < n; i++){
		mask[i] = 0;
	}
	for(int i = 0; i < n; i++){
		for(int j : g[i]){
			if(bits.count(j)){
				int p = 0;
				while( j != bito[p])p++;
				mask[i] += (1<<p);
			}
		}
	}
	vec < pii > edges;
	for(int i = 1; i <= n; i++){
		for( int j : g[i]){
			if(j > i && (!aux.count(i)) && (!aux.count(j))){
				edges.pb({i,j});
			}
		}
	}
	InitMap(n-12,edges.size());
	for(pii ed : edges){
		MakeMap(mask[ed.fr],mask[ed.sc]);
	}

}

/*int main(){
	fast;

}*/

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6912 KB Output is correct
2 Incorrect 13 ms 6912 KB Wrong Answer [11]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6912 KB Output is correct
2 Incorrect 13 ms 6912 KB Wrong Answer [11]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 754 ms 30872 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -