| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833105 |
2023-08-22T00:53:50 Z |
Lobo |
Simurgh (IOI17_simurgh) |
C++17 |
|
163 ms |
5292 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = 550;
const int maxm = maxn*maxn/2;
int n, m, h[maxn], mark[maxn], U[maxm], V[maxm];
pair<int,int> low[maxn];
vector<int> g[maxn], span, ins, outs;
int par[maxn], pari[maxn], is_span[maxm];
int in[maxm], out[maxm];
int queryspan;
int ds[maxn], dsz[maxn];
int find(int v) {
if(v == ds[v]) return v;
return ds[v] = find(ds[v]);
}
void join(int u, int v) {
if(dsz[u] < dsz[v]) swap(u,v);
dsz[u]+= dsz[v];
ds[v] = u;
}
vector<int> construct(vector<int> edges) {
vector<int> finaledges;
for(int i = 0; i < n; i++) {
ds[i] = i;
dsz[i] = 1;
}
for(auto i : edges) {
int u = find(U[i]);
int v = find(V[i]);
if(u != v) {
join(u,v);
finaledges.pb(i);
}
}
return finaledges;
}
void dfslow(int u, int ant) {
mark[u] = 1;
low[u] = mp(h[u],-1);
for(auto i : g[u]) {
int v = U[i]+V[i]-u;
if(v == ant) continue;
if(!mark[v]) {
h[v] = h[u]+1;
par[v] = u;
pari[v] = i;
span.pb(i);
is_span[i] = 1;
dfslow(v,u);
low[u] = min(low[u],low[v]);
}
else {
low[u] = min(low[u],mp(h[v],i));
}
}
}
void dfs(int u, int ant) {
for(auto i : g[u]) {
int v = U[i]+V[i]-u;
if(v == ant || is_span[i] == 0) continue;
dfs(v,u);
}
if(u == 0 || in[pari[u]] || out[pari[u]]) return;
if(low[u] == mp(h[u],-1)) {
in[pari[u]] = 1;
ins.pb(pari[u]);
}
else {
int ilow = low[u].sc;
int ulow = U[ilow];
int vlow = V[ilow];
if(h[ulow] > h[vlow]) swap(ulow,vlow);
int v = vlow;
vector<int> edges;
while(v != ulow) {
edges.pb(pari[v]);
v = par[v];
}
int know = -1;
for(auto i : edges) {
if(in[i] || out[i]) {
know = i;
}
}
// cout << u << " " << ilow << " - " << count_common_roads(construct(span)) << endl;
if(know == -1) {
vector<pair<int,int>> cons;
cons.pb(mp(queryspan,ilow));
for(auto i : edges) {
vector<int> doquery;
for(auto j : span) {
if(j != i) doquery.pb(j);
}
doquery.pb(ilow);
cons.pb(mp(count_common_roads(construct(doquery)),i));
}
sort(all(cons));
if(cons[0].fr == cons.back().fr) {
// todo mundo out / 0
out[ilow] = 1; outs.pb(ilow);
for(auto i : edges) {
out[i] = 1; outs.pb(i);
}
}
else {
for(auto X : cons) {
int i = X.sc;
if(X.fr < cons.back().fr) {
// in / 1
in[i] = 1; ins.pb(i);
}
else {
// out / 0
out[i] = 1; outs.pb(i);
}
}
}
}
else {
vector<pair<int,int>> cons;
cons.pb(mp(queryspan,ilow));
vector<int> doquery;
for(auto i : edges) {
if(i != pari[u]) {
doquery.pb(i);
}
}
doquery.pb(ilow);
cons.pb(mp(count_common_roads(construct(doquery)),pari[u]));
doquery.clear();
for(auto i : edges) {
if(i != know) {
doquery.pb(i);
}
}
doquery.pb(ilow);
cons.pb(mp(count_common_roads(construct(doquery)),know));
doquery.clear();
if(in[know]) {
if(cons[0].fr == cons[2].fr) {
in[ilow] = 1; ins.pb(ilow);
}
else {
out[ilow] = 1; outs.pb(ilow);
}
if(cons[1].fr == cons[2].fr) {
in[pari[u]] = 1; ins.pb(pari[u]);
}
else {
out[pari[u]] = 1; outs.pb(pari[u]);
}
}
else {
if(cons[0].fr == cons[2].fr) {
out[ilow] = 1; outs.pb(ilow);
}
else {
in[ilow] = 1; ins.pb(ilow);
}
if(cons[1].fr == cons[2].fr) {
out[pari[u]] = 1; outs.pb(pari[u]);
}
else {
in[pari[u]] = 1; ins.pb(pari[u]);
}
}
}
}
}
vector<int> find_roads(int N, std::vector<int> UU, std::vector<int> VV) {
n = N;
m = UU.size();
for(int i = 0; i < m; i++) {
U[i] = UU[i];
V[i] = VV[i];
g[U[i]].pb(i);
g[V[i]].pb(i);
}
par[0] = -1;
pari[0] = -1;
dfslow(0,-1);
queryspan = count_common_roads(construct(span));
dfs(0,-1);
for(int u = 0; u < n; u++) {
int L = 0;
while(L < g[u].size()) {
int l = L;
int r = (int) g[u].size()-1;
int nx = -1;
while(l <= r) {
int mid = (l+r)>>1;
vector<int> doquery;
for(int i = 0; i <= mid; i++) doquery.pb(g[u][i]);
for(auto i : span) doquery.pb(i);
vector<int> used = construct(doquery);
int should = 0;
for(auto i : used) should+= in[i];
if(count_common_roads(used) > should) {
nx = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
if(nx == -1) break;
in[g[u][nx]] = 1; ins.pb(g[u][nx]);
L = nx+1;
}
}
assert(ins.size() >= n-1);
assert(count_common_roads(ins) == n-1);
return ins;
for(auto i : span) {
cout << i << " " << in[i] << " " << out[i] << endl;
}
return vector<int>{0};
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:218:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | while(L < g[u].size()) {
| ~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:2:
simurgh.cpp:247:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
247 | assert(ins.size() >= n-1);
| ~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
456 KB |
correct |
| 3 |
Correct |
0 ms |
340 KB |
correct |
| 4 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
456 KB |
correct |
| 3 |
Correct |
0 ms |
340 KB |
correct |
| 4 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
456 KB |
correct |
| 3 |
Correct |
0 ms |
340 KB |
correct |
| 4 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
0 ms |
340 KB |
correct |
| 3 |
Correct |
90 ms |
3692 KB |
correct |
| 4 |
Correct |
132 ms |
5148 KB |
correct |
| 5 |
Correct |
133 ms |
5164 KB |
correct |
| 6 |
Correct |
138 ms |
5188 KB |
correct |
| 7 |
Correct |
134 ms |
5292 KB |
correct |
| 8 |
Correct |
134 ms |
5236 KB |
correct |
| 9 |
Correct |
137 ms |
5104 KB |
correct |
| 10 |
Correct |
131 ms |
5212 KB |
correct |
| 11 |
Correct |
163 ms |
5272 KB |
correct |
| 12 |
Correct |
134 ms |
5184 KB |
correct |
| 13 |
Correct |
0 ms |
340 KB |
correct |
| 14 |
Correct |
146 ms |
5120 KB |
correct |
| 15 |
Correct |
132 ms |
5148 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
correct |
| 2 |
Correct |
1 ms |
456 KB |
correct |
| 3 |
Correct |
0 ms |
340 KB |
correct |
| 4 |
Incorrect |
0 ms |
340 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
