Submission #828525

#	Time	Username	Problem	Language	Result	Execution time	Memory
828525		tolbi	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	212 KiB

simurgh

#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define coutara(x,y) for (auto &it : x) cout<<it<<" ";cout<<y<<endl;
#include "simurgh.h"
int ask(set<int> &st){
	vector<int> askarr;
	auto it = st.begin();
	while (it!=st.end()){
		askarr.push_back(*it);
		it++;
	}
	int ans = count_common_roads(askarr);
	return ans;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector<vector<int>> arr(n);
	int m = u.size();
	map<pair<int,int>,int> mp;
	for (int i = 0; i < m; i++){
		arr[u[i]].push_back(v[i]);
		arr[v[i]].push_back(u[i]);
		mp[{u[i],v[i]}]=i;
	}
	auto getindex = [&](pair<int,int> pr){
		if (mp.count(pr)) return mp[pr];
		swap(pr.first,pr.second);
		return mp[pr];
	};
	vector<int> par(n);
	vector<bool> vis(n,false);
	set<int> askarr;
	vector<int> dept(n);
	vector<int> origset;
	auto dfs = [&](int node, auto dfs)->void{
		vis[node]=true;
		for (int i = 0; i < arr[node].size(); i++){
			if (vis[arr[node][i]]) continue;
			par[arr[node][i]]=node;
			dept[arr[node][i]]=dept[node]+1;
			askarr.insert(getindex({node,arr[node][i]}));
			origset.push_back(getindex({node,arr[node][i]}));
			dfs(arr[node][i],dfs);
		}
	};
	dept[0]=0;
	dfs(0,dfs);
	int origans = ask(askarr);
	vector<int> hueh(m,1);
	for (int i = 0; i < m; i++){
		if (askarr.find(i)!=askarr.end()) continue;
		int a = u[i];
		int b = v[i];
		vector<int> yep;
		vector<int> nop;
		vector<int> idk;
		int art=0, azal=0, kal=0;
		bool yesb=false;
		bool hehheh = true;
		while (a!=b){
			if (dept[a]<dept[b]) swap(a,b);
			if (hueh[getindex({a,par[a]})]==1){
				hehheh=false;
				break;
			}
			a=par[a];
		}
		if (hehheh) continue;
		a=u[i],b=v[i];
		hehheh=false;
		while (a!=b){
			if (dept[a]<dept[b]) swap(a,b);
			if (hueh[getindex({a,par[a]})]!=1){
				askarr.erase(getindex({a,par[a]}));
				askarr.insert(i);
				yesb=hueh[getindex({a,par[a]})];
				hueh[i]=hueh[getindex({a,par[a]})];
				int crnum = ask(askarr);
				if (crnum!=origans){
					yesb=!yesb;
					hueh[i]=2-hueh[i];
				}
				askarr.erase(i);
				askarr.insert(getindex({a,par[a]}));
				hehheh=true;
				break;
			}
			a=par[a];
		}
		a=u[i],b=v[i];
		if (hehheh){
			while (a!=b){
				if (dept[a]<dept[b]) swap(a,b);
				if (hueh[getindex({a,par[a]})]==1){
					askarr.erase(getindex({a,par[a]}));
					askarr.insert(i);
					int crnum = ask(askarr);
					hueh[getindex({a,par[a]})]=hueh[i];
					if (crnum!=origans){
						hueh[getindex({a,par[a]})]=2-hueh[getindex({a,par[a]})];
					}
					askarr.insert(getindex({a,par[a]}));
					askarr.erase(i);
				}
				a=par[a];
			}
			continue;
		}
		while (a!=b){
			if (dept[a]<dept[b]) swap(b,a);
			askarr.erase(getindex({a,par[a]}));
			askarr.insert(i);
			int crnum = ask(askarr);
			if (crnum>origans){
				nop.push_back(getindex({a,par[a]}));
				yesb=true;
			}
			else if (crnum<origans){
				yep.push_back(getindex({a,par[a]}));
			}
			else {
				idk.push_back(getindex({a,par[a]}));
			}
			askarr.erase(i);
			askarr.insert(getindex({a,par[a]}));
			a=par[a];
		}
		if (yesb==true){
			while (idk.size()){
				yep.push_back(idk.back());
				idk.pop_back();
			}
		}
		else {
			while (idk.size()){
				nop.push_back(idk.back());
				idk.pop_back();
			}
		}
		if (yesb) hueh[i]=2;
		else hueh[i]=0;
		while (nop.size()){
			hueh[nop.back()]=0;
			nop.pop_back();
		}
		while (yep.size()){
			hueh[yep.back()]=2;
			yep.pop_back();
		}
	}
	//origdekiler updli yesb
	//O(n) till now
	//coutarr(hueh);
	vector<int> final;
	for (int i = 0; i < m; i++){
		if (final.size()==n-1) return final;
		if (hueh[i]==1){
			int a = u[i];
			int b = v[i];
			if (dept[a]<dept[b]) swap(a,b);
			askarr.erase(getindex({a,par[a]}));
			askarr.insert(i);
			int crnum = 0;
			hueh[i]=hueh[getindex({a,par[a]})];
			if (crnum!=origans){
				hueh[i]=2-hueh[i];
			}
			askarr.insert(getindex({a,par[a]}));
			askarr.erase(i);
		}
		if (hueh[i]==2) final.push_back(i);
	}
	/*yaani 3 dk kalmis ben nabayim artik
	for (int i = 0; i < n; ++i)
	{
		arr[i].clear():
	}
	for (int i = 0; i < m; i++){
		if (hueh[i]!=1) continue;
		arr[u[i]].push_back(v[i]);
		arr[v[i]].push_back(u[i]);
	}
	*/
	return final;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:57:7: warning: unused variable 'art' [-Wunused-variable]
   57 |   int art=0, azal=0, kal=0;
      |       ^~~
simurgh.cpp:57:14: warning: unused variable 'azal' [-Wunused-variable]
   57 |   int art=0, azal=0, kal=0;
      |              ^~~~
simurgh.cpp:57:22: warning: unused variable 'kal' [-Wunused-variable]
   57 |   int art=0, azal=0, kal=0;
      |                      ^~~
simurgh.cpp:156:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  156 |   if (final.size()==n-1) return final;
      |       ~~~~~~~~~~~~^~~~~
simurgh.cpp: In instantiation of 'find_roads(int, std::vector<int>, std::vector<int>)::<lambda(int, auto:23)> [with auto:23 = find_roads(int, std::vector<int>, std::vector<int>)::<lambda(int, auto:23)>]':
simurgh.cpp:47:11:   required from here
simurgh.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30