Submission #232143

#	Time	Username	Problem	Language	Result	Execution time	Memory
232143		kshitij_sodani	Triangles (CEOI18_tri)	C++17	0 / 100	7 ms	768 KiB

tri

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+"a.txt").c_str(),"w",stdout);
}
mt19937 rng;


int n,m;
int vis[301];
int vis3[301];
int vis2[501];
vector<int> adj[301];
int l;
int aa,bb;
set<pair<pair<int,int>,int>> cc;
int ans[301];
pair<int,int> loc[301];
pair<int,int> loc2[501];
int sect(int ac,int bc,int cc,int dc){
	if(min(loc2[ac].a,loc2[bc].a)<=min(loc2[cc].a,loc2[dc].a) and min(loc2[cc].a,loc2[dc].a)<=max(loc2[ac].a,loc2[bc].a) and max(loc2[ac].a,loc2[bc].a) <=max(loc2[cc].a,loc2[dc].a)){
		if(min(loc2[ac].b,loc2[bc].b)<=min(loc2[cc].b,loc2[dc].b) and min(loc2[cc].b,loc2[dc].b)<=max(loc2[ac].b,loc2[bc].b) and max(loc2[ac].b,loc2[bc].b) <=max(loc2[cc].b,loc2[dc].b)){
			return 1;

		}
		else if(max(loc2[ac].b,loc2[bc].b)>=max(loc2[cc].b,loc2[dc].b) and max(loc2[cc].b,loc2[dc].b)>=min(loc2[ac].b,loc2[bc].b) and min(loc2[ac].b,loc2[bc].b) >=min(loc2[cc].b,loc2[dc].b)){
			return 1;

		}
		else{
			return 0;
		}
	}
	else if(max(loc2[ac].a,loc2[bc].a)>=max(loc2[cc].a,loc2[dc].a) and max(loc2[cc].a,loc2[dc].a)>=min(loc2[ac].a,loc2[bc].a) and min(loc2[ac].a,loc2[bc].a) >=min(loc2[cc].a,loc2[dc].a)){
		if(min(loc2[ac].b,loc2[bc].b)<=min(loc2[cc].b,loc2[dc].b) and min(loc2[cc].b,loc2[dc].b)<=max(loc2[ac].b,loc2[bc].b) and max(loc2[ac].b,loc2[bc].b) <=max(loc2[cc].b,loc2[dc].b)){
			return 1;
		}
		else if(max(loc2[ac].b,loc2[bc].b)>=max(loc2[cc].b,loc2[dc].b) and max(loc2[cc].b,loc2[dc].b)>=min(loc2[ac].b,loc2[bc].b) and min(loc2[ac].b,loc2[bc].b) >=min(loc2[cc].b,loc2[dc].b)){
			return 1;

		}
		else{
			return 0;
		}
	}
	else{
		return 0;
	}
}
bool cmp(int k,int l){
	return loc2[k]<loc2[l];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(vis,0,sizeof(vis));
	memset(vis2,0,sizeof(vis2));
	memset(vis3,0,sizeof(vis3));
			setIO("1");
	
	
		rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
		cin>>n>>m;
		for(int i=0;i<m;i++){
			cin>>aa>>bb;
			adj[aa-1].pb(bb-1);
			adj[bb-1].pb(aa-1);
		}
		for(int i=0;i<n;i++){
			shuffle(adj[i].begin(),adj[i].end(),rng);
		}
		cin>>l;
		for(int i=0;i<l;i++){
			cin>>aa>>bb;
			loc2[i]={aa,bb};
		}
		vector<int> kk;
		vector<int> ll;
		/*for(int i=0;i<n;i++){
			kk.pb(i);
		}*/

		for(int i=0;i<l;i++){
			ll.pb(i);
		}
		sort(ll.begin(),ll.end(),cmp);
	//	shuffle(kk.begin(),kk.end(),rng);
	//	shuffle(ll.begin(),ll.end(),rng);
		int tot2=0;
		/*for(auto j:ll){
			cout<<j<<":";
		}
		cout<<endl;*/
		//vector<int> kk;
		for(int i=0;i<1;i++){
			int lo=rng()%n;
			if(vis3[lo]==0){
				vis3[lo]=1;
				kk.pb(lo);
			}
		}
		/*kk.pb(rng()%n);
		vis3[kk[0]]=1;*/
		vector<pair<int,int>> cur;
		for(int i=0;i<n;i++){
			pair<int,int> ans3={10000000,-1};
			for(int j=0;j<l;j++){
				if(vis2[ll[j]]==0){
					int tot=0;
					for(auto kko:adj[kk[i]]){
						if(vis[kko]){
							for(auto l:cur){
								if(kko==l.a or kko==l.b){
									continue;
								}
							//	cout<<kk[i]<<','<<kko<<","<<l.a<<','<<l.b<<endl;
								int ba=tot;
								tot+=sect(ll[j],ans[kko],ans[l.a],ans[l.b]);
								/*if(tot>ba){
									cout<<ll[j]<<","<<ans[kko]<<","<<ans[l.a]<<","<<ans[l.b]<<endl;
								}*/
							}
						}
					}

					if(tot<ans3.a){
						ans3={tot,ll[j]};
					}
				}
			}
			tot2+=ans3.a;
			vis[kk[i]]=1;
			for(auto j:adj[kk[i]]){
				if(vis[j]){
					cur.pb({kk[i],j});
				}
			}
			vis2[ans3.b]=1;

			ans[kk[i]]=ans3.b;
		//	cout<<kk[i]<<","<<ans3.b<<","<<ans3.a<<endl;
			for(auto j:adj[kk[i]]){
				if(vis3[j]==0){
					kk.pb(j);
					vis3[j]=1;
				}
			}
		}
	//	cout<<tot2<<endl;
		set<int> ss;
		int tot3=0;
		for(auto i:cur){
			for(int k=0;k<cur.size();k++){
				pair<int,int> j=cur[k];
				if(i.a==j.a or i.b==j.b or i.b==j.a or i.a==j.b){

				}
				else{
					tot3+=sect(ans[i.a],ans[i.b],ans[j.a],ans[j.b]);
				}
			}
		}
	//	cout<<tot3<<endl;
		for(int i=0;i<n;i++){


			cout<<ans[i]+1<<endl;

		}

	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:125:13: warning: unused variable 'ba' [-Wunused-variable]
         int ba=tot;
             ^~
tri.cpp:161:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<cur.size();k++){
                ~^~~~~~~~~~~
tri.cpp: In function 'void setIO(std::__cxx11::string)':
tri.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((name+".in").c_str(),"r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((name+"a.txt").c_str(),"w",stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25