#include "simurgh.h"
//#include "grader.cpp"
#include <set>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 505;
struct DSU
{
int parent[MAXN*MAXN];
int color[MAXN*MAXN];
DSU(){}
DSU(int n)
{
for(int i = 0;i<=n;i++)
{
this->parent[i] = i;
this->color[i] = -1;
}
}
int Find(int x)
{
if(parent[x]==x) return x;
parent[x] = Find(parent[x]);
return parent[x];
}
bool UnionSimple(int u, int v)
{
u = Find(u);
v = Find(v);
if(u==v) return false;
parent[v] = u;
return true;
}
bool UnionFull(int u, int v)
{
u = Find(u);
v = Find(v);
if(u==v) return false;
int newColor = max(color[u], color[v]);
color[u] = newColor;
color[v] = newColor;
parent[v] = u;
return true;
}
int getColor(int x)
{
return color[Find(x)];
}
int colorize(int x, int col)
{
x = Find(x);
color[x] = col;
}
};
DSU relationKeeper;
int n;
vector <pair <int, int>> edges;
set <int> constructST()
{
DSU T(n);
set <int> ST;
for(int i = 0;i<edges.size();i++)
{
if(relationKeeper.getColor(i)==1)
{
T.UnionSimple(edges[i].first, edges[i].second);
ST.insert(i);
}
}
for(int i = 0;i<edges.size();i++)
{
if(relationKeeper.getColor(i)!=0 && T.UnionSimple(edges[i].first, edges[i].second)==true)
{
ST.insert(i);
}
}
return ST;
}
int askVector(vector <int> v)
{
return count_common_roads(v);
}
int askSet(set <int> s)
{
vector <int> v;
for(int x: s) v.push_back(x);
return count_common_roads(v);
}
vector <int> getReplacements(set <int> ST, int e)
{
DSU T(n);
ST.erase(e);
for(int edgeInd: ST)
T.UnionSimple(edges[edgeInd].first, edges[edgeInd].second);
vector <int> out;
for(int i = 0;i<edges.size();i++)
{
if(i==e) continue;
if(T.Find(edges[i].first)==T.Find(edges[i].second)) continue;
out.push_back(i);
}
return out;
}
int getDiff(set <int> ST, int e1, int e2, int base)
{
ST.erase(e1);
ST.insert(e2);
int res = askSet(ST);
if(base==res) return 0;
if(base<res) return 1;
if(base>res) return 2;
}
int processDif(int e1, int e2, int diff)
{
if(diff==0)
{
relationKeeper.UnionFull(e1, e2);
}
else if(diff==1)
{
relationKeeper.colorize(e1, 0);
relationKeeper.colorize(e2, 1);
}
else if(diff==2)
{
relationKeeper.colorize(e1, 1);
relationKeeper.colorize(e2, 0);
}
}
vector <int> set2Vector(set <int> s)
{
vector <int> out;
for(int x: s) out.push_back(x);
return out;
}
vector<int> find_roads(int N, vector<int> U, vector<int> V)
{
n = N;
for(int i = 0;i<U.size();i++) edges.push_back({U[i], V[i]});
relationKeeper = DSU(U.size());
for(int iter = 0;iter<=n;iter++)
{
set <int> ST = constructST();
//cout << "currST: ";
//for(int x: ST) cout << " " << x;
//cout << '\n';
int royalCnt = askSet(ST);
if(royalCnt==n-1) return set2Vector(ST);
int e = -1;
for(int edgeInd: ST)
{
if(relationKeeper.getColor(edgeInd)==-1)
{
e = edgeInd;
break;
}
}
if(e==-1) return {};
//cout << " --- " << e << " --- " << '\n';
vector <int> replacements = getReplacements(ST, e);
//cout << "replacements:";
//for(int x: replacements) cout << " " << x;
//cout << '\n';
for(int edgeInd: replacements)
{
if(relationKeeper.getColor(edgeInd)!=-1)
{
int diff = getDiff(ST, e, edgeInd, royalCnt);
processDif(e, edgeInd, diff);
}
}
if(relationKeeper.getColor(e)==-1)
{
for(int edgeInd: replacements)
{
int diff = getDiff(ST, e, edgeInd, royalCnt);
processDif(e, edgeInd, diff);
}
if(relationKeeper.getColor(e)==-1)
{
for(int edgeInd: replacements)
relationKeeper.colorize(edgeInd, 1);
}
}
//cout << "color of " << e << " is " << relationKeeper.getColor(e) << '\n';
}
return {};
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
Compilation message
simurgh.cpp: In member function 'int DSU::colorize(int, int)':
simurgh.cpp:68:5: warning: no return statement in function returning non-void [-Wreturn-type]
68 | }
| ^
simurgh.cpp: In function 'std::set<int> constructST()':
simurgh.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
simurgh.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> getReplacements(std::set<int>, int)':
simurgh.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i = 0;i<edges.size();i++)
| ~^~~~~~~~~~~~~
simurgh.cpp: In function 'int processDif(int, int, int)':
simurgh.cpp:161:1: warning: no return statement in function returning non-void [-Wreturn-type]
161 | }
| ^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:174:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int i = 0;i<U.size();i++) edges.push_back({U[i], V[i]});
| ~^~~~~~~~~
simurgh.cpp: In function 'int getDiff(std::set<int>, int, int, int)':
simurgh.cpp:143:1: warning: control reaches end of non-void function [-Wreturn-type]
143 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2304 KB |
correct |
| 2 |
Runtime error |
6 ms |
4640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4480 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
