| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 828525 |
2023-08-17T10:48:12 Z |
tolbi |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
212 KB |
#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
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++){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
