| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1069308 |
2024-08-21T19:12:03 Z |
Ahmed57 |
Simurgh (IOI17_simurgh) |
C++17 |
|
2 ms |
8540 KB |
#include "bits/stdc++.h"
#include "simurgh.h"
using namespace std;
#pragma GCC optimize("Ofast")
int vis[100001];
int dep[100001];
pair<int,int> mi[100001];
pair<int,int> PR[100001];
vector<pair<int,int>> adj[100001];
vector<pair<int,int>> back[100001];
vector<pair<int,int>> tree[100001];
vector<int> tr;
vector<pair<int,int>> edg;
void dfs(int i,int pr){
vis[i] = 1;
dep[i] = dep[pr]+1;
mi[i] = {-1,-1};
for(auto j:adj[i]){
if(vis[j.first]&&dep[j.first]<dep[i]){
if(mi[i].first==-1)mi[i] = {i,j.first};
else if(dep[j.first]<dep[mi[i].second])mi[i] = {i,j.first};
back[i].push_back(j);continue;
}
PR[j.first] = {i,j.second};
tree[i].push_back(j);
dfs(j.first,i);
tr.push_back(j.second);
if(mi[i].first==-1)mi[i] = mi[j.first];
else if(mi[j.first].first!=-1&&dep[mi[j.first].second]<dep[mi[i].second])mi[i] = mi[j.first];
}
}
int p[100001],n;
int ans[100001];
int find(int x){
if(x==p[x])return x;
return p[x] = find(p[x]);
}
void mergegroup(int a,int b){
a = find(a);b = find(b);
if(a==b)return ;
p[a] = b;
}
int que(vector<int> v,bool ss){
for(int i = 0;i<n;i++){
p[i] = i;
}
for(int i = 0;i<v.size();i++){
mergegroup(edg[v[i]].first,edg[v[i]].second);
}
int all = 0;
for(auto i:tr){
if(find(edg[i].first)!=find(edg[i].second)){
v.push_back(i);
all+=ans[i];
mergegroup(edg[i].first,edg[i].second);
}
}
if(ss)all = count_common_roads(v)-all;
else all = count_common_roads(v);
return all;
}
void answer(int i){
for(auto j:tree[i]){
if(ans[j.second]!=-1)continue;
int lol = mi[j.first].second;
if(lol==-1||dep[lol]>dep[i]){
ans[j.second] = 1;
}else{
int st = mi[j.first].first;
vector<int> v;
while(st!=lol){
v.push_back(PR[st].second);
st = PR[st].first;
}
for(auto e:back[mi[j.first].first]){
if(e.first==lol){
v.push_back(e.second);
break;
}
}
int ma = -1;
for(auto e:v){
if(ans[e]==0){
vector<int> Q;
for(int w:v){
if(w==e)continue;
Q.push_back(w);
}
ma = que(Q,0);
break;
}
}
if(ma!=-1){
for(auto e:v){
if(ans[e]==-1){
vector<int> Q;
for(int w:v){
if(w==e)continue;
Q.push_back(w);
}
if(ma==que(Q,0)){
ans[e] = 1;
}else ans[e] = 0;
}
}
}else{
set<pair<int ,int >> s;
for(auto e:v){
if(ans[e]==-1){
vector<int> Q;
for(int w:v){
if(w==e)continue;
Q.push_back(w);
}
s.insert({que(Q,0),e});
}
}
int la = (*(--s.end())).first;
int sm = (*s.begin()).first;
if(la==sm){
for(auto w:s)ans[w.second] = 0;
}else{
for(auto w:s){
if(w.first==la)ans[w.second] = 0;
else ans[w.second] = 1;
}
}
}
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v){
for(int i = 0;i<u.size();i++){
ans[i] = -1;
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
edg.push_back({u[i],v[i]});
}
PR[0] = {-1,-1};
dfs(0,0);
answer(0);
for(int i = 0;i<n;i++){
int la = 0;
while(1){
if(la==back[i].size())break;
vector<int> Q;
for(int e = la;e<back[i].size();e++)Q.push_back(back[i][e].second);
if(que(Q,1)){
int l = la , r = back[i].size()-1 , ANS = 0;
while(l<=r){
int mid = (l+r)/2;
vector<int> Q;
for(int e = la;e<=mid;e++){
Q.push_back(back[i][e].second);
}
if(que(Q,1)){
ANS = mid;r = mid-1;
}else l = mid+1;
}
ans[back[i][ANS].second] = 1;
la = ANS+1;
}else break;
}
}
vector<int> good;
for(int i = 0;i<u.size();i++){
if(ans[i]==1){
good.push_back(i);
}
}
return good;
}
Compilation message
simurgh.cpp: In function 'int que(std::vector<int>, bool)':
simurgh.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = 0;i<u.size();i++){
| ~^~~~~~~~~
simurgh.cpp:146:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if(la==back[i].size())break;
| ~~^~~~~~~~~~~~~~~~
simurgh.cpp:148:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int e = la;e<back[i].size();e++)Q.push_back(back[i][e].second);
| ~^~~~~~~~~~~~~~~
simurgh.cpp:167:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int i = 0;i<u.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7512 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
