| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 404879 |
2021-05-15T08:30:09 Z |
b00n0rp |
Simurgh (IOI17_simurgh) |
C++17 |
|
185 ms |
7096 KB |
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define F first
#define S second
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
const int MX = 505;
int N;
vpii adj[MX];
vpii edges;
vi T;
vi ans;
int status[MX*MX];
bitset<MX> vis;
int dep[MX];
pii low[MX],par[MX];
void dfs(int u,int d){
vis[u] = 1;
dep[u] = d;
for(auto v:adj[u]){
if(vis[v.F] and dep[v.F] > d){
low[u] = min(low[u],low[v.F]);
}
else if(vis[v.F]){
low[u] = min(low[u],{dep[v.F],v.S});
}
else{
T.pb(v.S);
par[v.F] = {u,v.S};
low[v.F] = {d,v.S};
dfs(v.F,d+1);
}
}
}
int dsu_par[MX],dsu_rank[MX];
int find(int x){
if(dsu_par[x] == x) return dsu_par[x];
return dsu_par[x] = find(dsu_par[x]);
}
void merge(int u,int v){
u = find(u);
v = find(v);
if(dsu_rank[u] < dsu_rank[v]) swap(u,v);
dsu_par[v] = u;
dsu_rank[u]++;
}
int count(vi gg){
FOR(i,1,N+1){
dsu_par[i] = i;
dsu_rank[i] = 1;
}
for(auto x:gg) merge(edges[x].F,edges[x].S);
int precount = 0;
for(auto x:T){
if(find(edges[x].F) != find(edges[x].S)){
merge(edges[x].F,edges[x].S);
gg.pb(x);
precount += status[x];
}
}
return count_common_roads(gg)-precount;
}
void solve(vi gg,int k){
if(k == 0) return;
if(gg.size() == k){
for(auto x:gg){
status[x] = 1;
}
return;
}
vi gg1,gg2;
REP(i,gg.size()){
if(i < gg.size()/2) gg1.pb(gg[i]);
else gg2.pb(gg[i]);
}
int c = count(gg1);
solve(gg1,c);
solve(gg2,k-c);
}
vi find_roads(int n, vi u, vi v) {
N = n;
int m = u.size();
REP(i,m){
u[i]++;
v[i]++;
adj[u[i]].pb({v[i],i});
adj[v[i]].pb({u[i],i});
edges.pb({u[i],v[i]});
}
vis.reset();
par[1] = {1,-1};
low[1] = {0,-1};
dfs(1,0);
sort(T.begin(),T.end());
REP(i,m) status[i] = -1;
int basic = count_common_roads(T);
FOR(i,1,n+1){
if(low[i].S != -1 and (!binary_search(T.begin(),T.end(),low[i].S))){
// cout << i << " " << low[i].F << " " << low[i].S << "\n";
int cur = i;
vi known;
vi unknown;
while(dep[cur] != low[i].F){
if(status[par[cur].S] == -1) unknown.pb(par[cur].S);
else known.pb(par[cur].S);
cur = par[cur].F;
}
if(unknown.empty()) continue;
if(known.empty()){
vpii bruh;
int mn = basic,mx = basic;
for(auto y:unknown){
vi gg;
gg.pb(low[i].S);
for(auto x:T){
if(x != y) gg.pb(x);
}
bruh.pb({y,count_common_roads(gg)});
mn = min(mn,bruh.back().S);
mx = max(mx,bruh.back().S);
}
if(mn == mx){
for(auto y:unknown) status[y] = 0;
}
else{
for(auto y:bruh){
if(y.S == mn) status[y.F] = 1;
else status[y.F] = 0;
}
}
}
else{
vi gg;
gg.pb(low[i].S);
for(auto x:T){
if(x != known[0]) gg.pb(x);
}
int roy = count_common_roads(gg)-(basic-status[known[0]]);
for(auto y:unknown){
gg.clear();
gg.pb(low[i].S);
for(auto x:T){
if(x != y) gg.pb(x);
}
status[y] = basic-count_common_roads(gg)-roy;
}
}
}
}
// cout << "yo\n";
FOR(i,1,n+1){
vi gg;
for(auto x:adj[i]){
if(x.F > i) gg.pb(x.S);
}
solve(gg,count(gg));
}
REP(i,m){
if(status[i] == 1){
ans.pb(i);
// cout << i << "\n";
}
}
return ans;
}
Compilation message
simurgh.cpp: In function 'void solve(std::vector<int>, int)':
simurgh.cpp:79:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
79 | if(gg.size() == k){
| ~~~~~~~~~~^~~~
simurgh.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define REP(i,n) for(int i = 0; i < n; i ++)
......
86 | REP(i,gg.size()){
| ~~~~~~~~~~~
simurgh.cpp:86:2: note: in expansion of macro 'REP'
86 | REP(i,gg.size()){
| ^~~
simurgh.cpp:87:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if(i < gg.size()/2) gg1.pb(gg[i]);
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
13 ms |
4948 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
13 ms |
4948 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
13 ms |
4948 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
113 ms |
4988 KB |
correct |
| 4 |
Correct |
176 ms |
6896 KB |
correct |
| 5 |
Correct |
182 ms |
7008 KB |
correct |
| 6 |
Correct |
172 ms |
6996 KB |
correct |
| 7 |
Correct |
113 ms |
7020 KB |
correct |
| 8 |
Correct |
131 ms |
6992 KB |
correct |
| 9 |
Correct |
173 ms |
7028 KB |
correct |
| 10 |
Correct |
185 ms |
6968 KB |
correct |
| 11 |
Correct |
184 ms |
7096 KB |
correct |
| 12 |
Correct |
182 ms |
6968 KB |
correct |
| 13 |
Correct |
1 ms |
204 KB |
correct |
| 14 |
Correct |
156 ms |
6968 KB |
correct |
| 15 |
Correct |
179 ms |
6968 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
correct |
| 2 |
Incorrect |
13 ms |
4948 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
