oj.uz

Submission #396121

# Submission time Handle Problem Language Result Execution time Memory
396121 2021-04-29T13:27:17 Z nathanlee726 Airline Route Map (JOI18_airline) C++14
0 / 100
 804 ms 25240 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 4728 KB Output is correct
2 Correct 6 ms 4732 KB Output is correct
3 Correct 5 ms 4728 KB Output is correct
4 Incorrect 5 ms 4596 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 4728 KB Output is correct
2 Correct 6 ms 4732 KB Output is correct
3 Correct 5 ms 4728 KB Output is correct
4 Incorrect 5 ms 4596 KB Wrong Answer [11]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 25240 KB Output is correct : V - N = 12
2 Correct 514 ms 21436 KB Output is correct : V - N = 12
3 Correct 273 ms 11860 KB Output is correct : V - N = 12
4 Correct 14 ms 5040 KB Output is correct : V - N = 12
5 Correct 128 ms 8784 KB Output is correct : V - N = 12
6 Correct 589 ms 19428 KB Output is correct : V - N = 12
7 Correct 740 ms 24952 KB Output is correct : V - N = 12
8 Correct 754 ms 23460 KB Output is correct : V - N = 12
9 Correct 376 ms 13956 KB Output is correct : V - N = 12
10 Correct 39 ms 6000 KB Output is correct : V - N = 12
11 Correct 87 ms 6776 KB Output is correct : V - N = 12
12 Correct 438 ms 16120 KB Output is correct : V - N = 12
13 Correct 610 ms 23892 KB Output is correct : V - N = 12
14 Correct 752 ms 24412 KB Output is correct : V - N = 12
15 Correct 515 ms 18372 KB Output is correct : V - N = 12
16 Correct 119 ms 7596 KB Output is correct : V - N = 12
17 Correct 22 ms 5596 KB Output is correct : V - N = 12
18 Correct 237 ms 12804 KB Output is correct : V - N = 12
19 Correct 743 ms 22484 KB Output is correct : V - N = 12
20 Correct 804 ms 25032 KB Output is correct : V - N = 12
21 Correct 174 ms 10968 KB Output is correct : V - N = 12
22 Correct 130 ms 9208 KB Output is correct : V - N = 12
23 Correct 73 ms 6576 KB Output is correct : V - N = 12
24 Correct 8 ms 4856 KB Output is correct : V - N = 12
25 Correct 49 ms 5828 KB Output is correct : V - N = 12
26 Correct 151 ms 8692 KB Output is correct : V - N = 12
27 Correct 175 ms 10028 KB Output is correct : V - N = 12
28 Correct 207 ms 9568 KB Output is correct : V - N = 12
29 Correct 114 ms 7332 KB Output is correct : V - N = 12
30 Correct 12 ms 5028 KB Output is correct : V - N = 12
31 Incorrect 8 ms 4960 KB Wrong Answer [11]
32 Halted 0 ms 0 KB -