Submission #396054

# Submission time Handle Problem Language Result Execution time Memory
396054 2021-04-29T12:04:07 Z nathanlee726 Airline Route Map (JOI18_airline) C++14
0 / 100
398 ms 14644 KB
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
void Alice( int N, int M, int A[], int B[] );
void InitG( int V, int U );
void MakeG( int pos, int C, int D );
#else
#include "Alicelib.h"
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int n,m,c[500010],d[500010];
void Alice(int N,int M,int a[],int b[]){
	int n=N+12,m=0;
	F(n){
		Fi(j,10)if((i+1)&(1<<j)){c[m]=N+j+1,d[m]=i,m++;}
	}
	InitG(n,M+m+11);
	
	F(m)assert(c[i]!=d[i]);
	F(M)MakeG(i,a[i],b[i]);
	F(m)MakeG(M+i,c[i],d[i]);
	F(11)MakeG(M+m+i,N+i,N+i+1);
}
	//#include<i_am_noob_orz>
	#include<bits/stdc++.h>
	#include <ext/pb_ds/tree_policy.hpp>
	#include <ext/pb_ds/assoc_container.hpp>
	using namespace __gnu_pbds;
	using namespace std;
	#define ll long long
	//#define int ll
	#define ull unsigned long long
	#define pii pair<int,int>
	#define X first
	#define Y second
	#define mod ((ll)1e9+7)
	#define pb push_back
	#define mp make_pair
	#define abs(x) ((x)>0?(x):(-(x)))
	#define F(n) Fi(i,n)
	#define Fi(i,n) Fl(i,0,n)
	#define Fl(i,l,n) for(int i=l;i<n;i++)
	#define memres(a) memset(a,0,sizeof(a))
	#define all(a) a.begin(),a.end()
	#define sz(a) ((int)a.size())
	#define ceiling(a,b) (((a)+(b)-1)/(b))
	#define endl '\n'
	#define bit_count(x) __builtin_popcountll((x))
	#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	#define jimmy_is_kind false
	typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
	 
	//#define LOCAL
	#ifdef LOCAL
	#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
	template<typename T> void _do(T && x) {cerr<<x<<endl;}
	template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
	#define IOS()
	void Bob( int V, int U, int C[], int D[] );
	void InitMap( int N, int M );
	void MakeMap( int A, int B );
	#else
	#include "Boblib.h"
	#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
	#define endl '\n'
	#define bug(...)
	#endif
	 
	int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
	int sub(int a,int b){return(a<b?a+mod-b:a-b);}
	int po(int a,int b){
		if(b==0)return 1;
		if(b==1)return(a%mod);
		int tem=po(a,b/2);
		if(b&1)return(((tem*tem)%mod)*a)%mod;
		else return(tem*tem)%mod; 
	}
	int GCD(int a,int b){
		int x=0;
		int ra,rb;
		while(a&&b){
			if(((a&1)==0)&&((b&1)==0)){
				a>>=1,b>>=1,x++;
			}
			else if((a^b)&1){
				if(a&1)b>>=1;
				else a>>=1;
			}
			else{
				ra=abs(a-b),rb=min(a,b);
				a=ra,b=rb;
			}
		}
		return max(a,b)<<x;
	}
	int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
	vector<int> g[1050];
	int fr[1050],id[1050],idd[1050],c[500010],d[500010];
	bool vis[1050],tag[1050];
	void Bob(int N,int M,int a[],int b[]){
		int n=N-12,m=0;
		vector<int> v;
		F(M){
			g[a[i]].pb(b[i]);
		}
		F(N)if(sz(g[i])==1)v.pb(i);
		memres(tag);
		int s=v[0],t=v[1];
		tag[s]=1,tag[t]=1;
		s=g[s][0],t=g[t][0];
		if(sz(g[s])<sz(g[t]))swap(s,t);
		memres(vis);
		priority_queue<pii,vector<pii>,greater<pii> >pq; 
		vis[s]=1;
		pq.push({0,s});
		while(!pq.empty()){
			pii p=pq.top();pq.pop();
			for(int u:g[p.Y]){
				if(vis[u])continue;
				fr[u]=p.Y;
				pq.push({p.X+1,u});
				vis[u]=1;
			}
		}
		F(10){tag[t]=1;id[t]=9-i;t=fr[t];}
		F(N){
			if(tag[i])continue;
			int ind=0;
			for(int u:g[i]){
				if(tag[u]){
					ind+=id[u];
				}
			}
			idd[i]=ind;	
		}
		F(N){
			if(tag[i])continue;
			for(int u:g[i]){
				if(tag[u])continue;
				if(i<u){
					c[m]=idd[i];
					d[m]=idd[u];
					m++;
				}
			}
		}
		InitMap(n,m);
		F(m){
			MakeMap(c[i],d[i]);
		}
	}
# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 6600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 6600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 398 ms 14644 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -