oj.uz

Submission #396126

# Submission time Handle Problem Language Result Execution time Memory
396126 2021-04-29T13:34:25 Z nathanlee726 Airline Route Map (JOI18_airline) C++14
0 / 100
 905 ms 25060 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 InitG( int V, int U ){cout<<V<<" "<<U<<endl;}
void MakeG( int pos, int C, int D ){cout<<C<<" "<<D<<endl;}
#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 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++;}
	}
	F(9){
		c[m]=N+1+i,d[m]=N+2+i;
		m++;
	} 
	InitG(n,M+m+11);
	F(M)MakeG(i,a[i],b[i]);
	F(m)MakeG(M+i,c[i],d[i]);
	MakeG(M+m,N,N+11);
	F(10)MakeG(M+m+1+i,N+11,N+1+i); 
}
/*
int main(){
	int n,m,a[500],b[500];
	cin>>n>>m;
	F(m){
		cin>>a[i]>>b[i];
	}
	Alice(n,m,a,b);
	return 0;
}*/
/*
1
01
11
001
101
011
111
0001
*/
//#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 InitMap( int N, int M ){cout<<N<<" "<<M<<endl;}
void MakeMap( int A, int B ){cout<<A<<" "<<B<<endl;}
#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;
	/*if(n==1){
		InitMap(n,m);
		return;
	}*/
	vector<int> v;
	F(M){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	F(N)if(sz(g[i])==1)v.pb(i);
	memres(tag);
	int s=v[0],ms=s;
	s=g[s][0];
	int mn=1e9,mnp=-1;
	for(int u:g[s]){
		if(u==ms)continue;
		tag[u]=1;
		if(mn>sz(g[u]))mn=sz(g[u]),mnp=u;
	}
	memres(idd);
	id[mnp]=9;
	F(9){
		for(int u:g[mnp]){
			if(tag[u]&&id[u]==0){
				id[u]=8-i;
				bug(u,id[u]);
				mnp=u;
				break;
			}
		}
	}
	tag[s]=1,tag[ms]=1;
	F(N){
		if(tag[i])continue;
		int ind=0;
		for(int u:g[i]){
			if(tag[u]){
				ind+=(1<<id[u]);
			}
		}
		idd[i]=ind-1;	
	}
	F(N){
		if(tag[i])continue;
		for(int u:g[i]){
			if(tag[u])continue;
			if(i<u){
				bug(i,u);
				c[m]=idd[i];
				d[m]=idd[u];
				m++;
			}
		}
	}
	InitMap(n,m);
	F(m){
		MakeMap(c[i],d[i]);
	}
}
/*
int main(){
	int n,m,a[500],b[500];
	cin>>n>>m;
	F(m){
		cin>>a[i]>>b[i];
	}
	Bob(n,m,a,b);
	return 0;
}*/
/*
17 25
0 1
0 2
1 3
1 4
3 4
2 3
2 4
6 0
7 1
6 2
7 2
8 3
6 4
8 4
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

5 7
0 1
0 2
1 3
1 4
3 4
2 3
2 4
*/

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4624 KB Output is correct
2 Correct 6 ms 4624 KB Output is correct
3 Correct 6 ms 4788 KB Output is correct
4 Incorrect 6 ms 4696 KB Wrong Answer [11]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4624 KB Output is correct
2 Correct 6 ms 4624 KB Output is correct
3 Correct 6 ms 4788 KB Output is correct
4 Incorrect 6 ms 4696 KB Wrong Answer [11]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 25060 KB Output is correct : V - N = 12
2 Correct 656 ms 21576 KB Output is correct : V - N = 12
3 Correct 189 ms 11908 KB Output is correct : V - N = 12
4 Correct 13 ms 5024 KB Output is correct : V - N = 12
5 Correct 124 ms 8972 KB Output is correct : V - N = 12
6 Correct 575 ms 19480 KB Output is correct : V - N = 12
7 Correct 848 ms 24860 KB Output is correct : V - N = 12
8 Correct 603 ms 23140 KB Output is correct : V - N = 12
9 Correct 293 ms 13844 KB Output is correct : V - N = 12
10 Correct 35 ms 6048 KB Output is correct : V - N = 12
11 Correct 62 ms 6756 KB Output is correct : V - N = 12
12 Correct 442 ms 16180 KB Output is correct : V - N = 12
13 Correct 800 ms 23932 KB Output is correct : V - N = 12
14 Correct 611 ms 24336 KB Output is correct : V - N = 12
15 Correct 481 ms 18360 KB Output is correct : V - N = 12
16 Correct 106 ms 7712 KB Output is correct : V - N = 12
17 Correct 19 ms 5476 KB Output is correct : V - N = 12
18 Correct 335 ms 12908 KB Output is correct : V - N = 12
19 Correct 743 ms 22504 KB Output is correct : V - N = 12
20 Correct 905 ms 24968 KB Output is correct : V - N = 12
21 Correct 204 ms 11216 KB Output is correct : V - N = 12
22 Correct 142 ms 9200 KB Output is correct : V - N = 12
23 Correct 79 ms 6620 KB Output is correct : V - N = 12
24 Correct 8 ms 4920 KB Output is correct : V - N = 12
25 Correct 42 ms 5804 KB Output is correct : V - N = 12
26 Correct 112 ms 8560 KB Output is correct : V - N = 12
27 Correct 232 ms 10016 KB Output is correct : V - N = 12
28 Correct 191 ms 9756 KB Output is correct : V - N = 12
29 Correct 108 ms 7248 KB Output is correct : V - N = 12
30 Correct 12 ms 5140 KB Output is correct : V - N = 12
31 Incorrect 9 ms 4960 KB Wrong Answer [11]
32 Halted 0 ms 0 KB -