oj.uz

Submission #236326

# Submission time Handle Problem Language Result Execution time Memory
236326 2020-06-01T11:03:45 Z kshitij_sodani Airline Route Map (JOI18_airline) C++17
0 / 100
 2500 ms 30936 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second

#include "Alicelib.h"

map<int,int> x;
/*void InitG(int ac,int bc){
	cout<<ac<<" "<<bc<<endl;
}
void MakeG(int ac,int bc,int cc){
	cout<<bc<<" "<<cc<<endl;
}*/
void Alice(int n, int m, int aa[], int bb[]){
	for(int i=0;i<1000;i++){
		x[i]=i;
	}
	x[511]=1003;
	x[767]=1005;
	x[895]=1006;
	x[959]=1011;
	x[991]=1013;

	vector<pair<int,int>> ans;
	for(int i=0;i<m;i++){
		ans.pb({aa[i],bb[i]});
	}
	for(int ii=0;ii<n;ii++){
		int i=x[ii];
		for(int j=0;j<10;j++){
			if(i&(1<<j)){
				ans.pb({n+2+j,ii});
			}
		}
	}
	for(int i=0;i<n;i++){
		ans.pb({n+1,i});
	}
	for(int j=0;j<n+12;j++){
		if(j==n or j==n+1){
			continue;
		}
		ans.pb({n,j});
	}
	int co=8;
	for(int i=n+2;i<n+11;i++){
		ans.pb({i,i+1});
		/*for(int j=i+1;j<i+1+co;j++){
			ans.pb({i,j});
		}*/
		co-=2;
	}
	InitG(n+12,ans.size());
	int kk=0;
	for(auto j:ans){
		MakeG(kk,j.a,j.b);
		kk+=1;
	}

}

/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int no,mo;
	cin>>no>>mo;
	int cc[mo];
	int dd[mo];
	for(int i=0;i<mo;i++){
		cin>>cc[i]>>dd[i];
	}
	Alice(no,mo,cc,dd);

	return 0;
}*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "Boblib.h"
/*void InitMap(int ac,int bc){
	cout<<ac<<":"<<bc<<endl;
}
void MakeMap(int bc,int cc){
	cout<<bc<<","<<cc<<endl;
}
*/
map<int,int> x;
vector<int> adj[1012];
int mat[1012][1012];
int vis[1012];
void Bob(int nn, int m, int aa[], int bb[]){
	for(int i=0;i<1000;i++){
		x[i]=i;
	}
	for(int j=0;j<1012;j++){
		vis[j]=0;
	}
	for(int i=0;i<1012;i++){
		for(int j=0;j<1012;j++){
			mat[i][j]=0;
		}
	}
	for(int i=0;i<m;i++){
		mat[aa[i]][bb[i]]=1;
		mat[bb[i]][aa[i]]=1;
		adj[aa[i]].pb(bb[i]);
		adj[bb[i]].pb(aa[i]);
	}
	x[1003]=511;
	x[1005]=767;
	x[1006]=895;
	x[1011]=959;
	x[1013]=991;
	vector<int> pp={1003,1005,1006,1011,1013};
	int co[nn];
	for(int i=0;i<nn;i++){
		co[i]=0;
	}
	for(int i=0;i<m;i++){
		co[aa[i]]+=1;
		co[bb[i]]+=1;
	}
	int ind;
	for(int i=0;i<nn;i++){
		if(co[i]==nn-2){
			ind=i;
		}
	}
//	cout<<ind<<endl;
	int ind2;
	for(int j=0;j<nn;j++){
		if(j!=ind and mat[ind][j]==0){
			ind2=j;
		}
	}
//	cout<<ind2<<endl;
	vector<int> ext;
	for(int i=0;i<nn;i++){
		if(i==ind or i==ind2){
			continue;
		}
		if(mat[ind2][i]==0){
			ext.pb(i);
		}
	}
/*	for(auto j:ext){
		cout<<j<<":";
	}
	cout<<endl;*/
	for(int i=0;i<10;i++){
		vis[ext[i]]=1;
	}
	vis[ind]=1;
	vis[ind2]=1;

	/*if(ext.size()!=10){
		while(true){
			continue;
		}
	}*/
	int ext2[10];
	vector<int> co2[10];
	

	for(int ii=0;ii<ext.size();ii++){
		for(int jj=ii+1;jj<ext.size();jj++){
			int i=ext[ii];
			int j=ext[jj];
			if(i==j){
				continue;
			}
			if(mat[i][j]){
				co2[ii].pb(jj);
				co2[jj].pb(ii);
			}
		}
	}
	int ind3=-1;
	int ind4=-1;
	for(int i=0;i<10;i++){
		if(co2[i].size()==1){
			if(ind3==-1){
				ind3=i;
			}
			else{
				ind4=i;
			}
		}
	}
	int ko=0;
	for(int i=0;i<nn;i++){
		if(vis[i]==0 and mat[ind3][i]){
			ko+=1;
		}
	}
	int lo=0;
	for(int i=0;i<nn;i++){
		if(vis[i]==0 and mat[ind4][i]){
			lo+=1;
		}
	}

//	cout<<ind3<<"/"<<ind4<<endl;;
	if(ko<lo){
		swap(ind3,ind4);
	}
	ext2[0]=ind3;
	int prev=ind3;
	int cur=co2[ind3][0];
	for(int i=1;i<10;i++){
//		cout<<cur<<":"<<prev<<endl;
		int ind5=-1;
		for(auto j:co2[cur]){
			if(j!=prev){
				ind5=j;
				break;
			}
		}
		prev=cur;
		cur=ind5;
		ext2[i]=prev;

	}

	for(int i=0;i<10;i++){
		ext2[i]=ext[ext2[i]];
	//	cout<<ext2[i]<<",";
	}
	//cout<<endl;
	
	for(int i=0;i<10;i++){
		for(auto j:adj[ext2[i]]){
			if(vis[j]<=0){
				vis[j]-=(1<<i);
			}
		}
	}

	vector<pair<int,int>> ans;
	for(int i=0;i<nn;i++){
		for(int j=i+1;j<nn;j++){
			if(mat[i][j]==1 and vis[i]<=0 and vis[j]<=0){
				for(auto k:pp){
					if(vis[i]==-k or vis[j]==-k){
						while(true){
							continue;
						}
					}
				}
				ans.pb({x[-vis[i]],x[-vis[j]]});
			}
		}
	}
	InitMap(nn-12,ans.size());
	for(auto i:ans){
		MakeMap(i.a,i.b);
	}
}
/*
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int no,mo;
	cin>>no>>mo;
	int cc[mo];
	int dd[mo];
	for(int i=0;i<mo;i++){
		cin>>cc[i]>>dd[i];
	}
	Bob(no,mo,cc,dd);

	return 0;
}*/

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int ii=0;ii<ext.size();ii++){
               ~~^~~~~~~~~~~
Bob.cpp:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int jj=ii+1;jj<ext.size();jj++){
                   ~~^~~~~~~~~~~
Bob.cpp:82:10: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  vis[ind]=1;
  ~~~~~~~~^~
Bob.cpp:83:11: warning: 'ind2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  vis[ind2]=1;
  ~~~~~~~~~^~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 8968 KB Wrong Answer [120]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 8968 KB Wrong Answer [120]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3549 ms 30936 KB Time limit exceeded
2 Halted 0 ms 0 KB -