Submission #828504

#	Time	Username	Problem	Language	Result	Execution time	Memory
828504		tolbi	Simurgh (IOI17_simurgh)	C++17	30 / 100	139 ms	7960 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);
    	//coutara(askarr,ans);
    	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 hehhehe = 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);
    				int crnum = ask(askarr);
    				if (crnum>origans){
    					yesb=true;
    				}
    				else if (crnum<origans){
    					yesb=false;
    				}
    				else {
    					yesb=(hueh[getindex({a,par[a]})]);
    				}
    				askarr.erase(i);
    				askarr.insert(getindex({a,par[a]}));
    				break;
    			}
    			a=par[a];
    		}
          a=u[i],b=v[i];
    		if (hehhehe){
    			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);
    					if (crnum>origans){
    						hueh[getindex({a,par[a]})]=0;
    					}
    					else if (crnum<origans){
    						hueh[getindex({a,par[a]})]=2;
    					}
    					else {
    						hueh[getindex({a,par[a]})]=yesb*2;
    					}
    					askarr.erase(i);
    					askarr.insert(getindex({a,par[a]}));
    				}
    				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();
    		}
    	}
    	vector<int> final;
    	for (int i = 0; i < m; i++){
    		if (hueh[i]!=0) final.push_back(i);
    	}
    	//coutarr(final);
    	return final;
    }//wa?

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:58:11: warning: unused variable 'art' [-Wunused-variable]
   58 |       int art=0, azal=0, kal=0;
      |           ^~~
simurgh.cpp:58:18: warning: unused variable 'azal' [-Wunused-variable]
   58 |       int art=0, azal=0, kal=0;
      |                  ^~~~
simurgh.cpp:58:26: warning: unused variable 'kal' [-Wunused-variable]
   58 |       int art=0, azal=0, kal=0;
      |                          ^~~
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:48:15:   required from here
simurgh.cpp:38:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |       for (int i = 0; i < arr[node].size(); i++){
      |                       ~~^~~~~~~~~~~~~~~~~~

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