| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 790895 |
2023-07-23T09:18:47 Z |
ymm |
Simurgh (IOI17_simurgh) |
C++17 |
|
3000 ms |
340 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 242;
vector<pii> A[N], Ar[N];
int Am[N][N];
bitset<N> Abs[N], nvis;
int n;
namespace dsu {
int par[N];
void init() { memset(par, -1, sizeof(par)); }
int rt(int v) { return par[v] == -1? v : (par[v] = rt(par[v])); }
void unite(int v, int u) {
v = rt(v);
u = rt(u);
assert(v != u);
if (A[v].size() + Ar[v].size() < A[u].size() + Ar[u].size())
swap(v, u);
A[v].insert(A[v].end(), A[u].begin(), A[u].end());
Ar[v].insert(Ar[v].end(), Ar[u].begin(), Ar[u].end());
for (auto [x, e] : A[u]) {
Abs[v][x] = 1;
Am[v][x] = e;
}
for (auto [x, e] : Ar[u]) {
Abs[v][x] = 1;
Am[v][x] = e;
}
par[u] = v;
}
}
using dsu::rt;
vector<int> gold;
vector<int> cur;
int par[N];
int pare[N];
bool rem[N*N];
vector<int> cyc, cyce;
void make_cyc(int v, int u, int e) {
cyc.clear();
cyce.clear();
for (int x = v; x != u; x = par[x]) {
cyc.push_back(x);
cyce.push_back(pare[x]);
}
cyc.push_back(u);
cyce.push_back(e);
}
bool dfscyc(int v, int p, int pe) {
par[v] = p;
pare[v] = pe;
Loop (i,0,A[v].size()) {
auto [u, e] = A[v][i];
if (e == pe)
continue;
u = rt(u);
if (rem[e] || u == v) {
rem[e] = 1;
swap(A[v].back(), A[v][i]);
Ar[v].push_back(A[v].back());
A[v].pop_back();
--i;
continue;
}
if (par[u] != -1) {
make_cyc(v, u, e);
return 1;
}
if (dfscyc(u, v, e))
return 1;
}
return 0;
}
void dfs_tr(int v)
{
nvis[v] = 0;
int i = -1;
for (;;) {
int u = (nvis & Abs[v])._Find_next(i);
if (u >= n)
break;
int e = Am[v][u];
if (rem[e])
continue;
int r = rt(u);
nvis[u] = 0;
if (u != r && !nvis[r])
continue;
u = r;
nvis[u] = 0;
cur.push_back(e);
dfs_tr(u);
}
}
void test_cyc()
{
nvis.set();
for (int v : cyc)
nvis[v] = 0;
cur.clear();
for (int v : cyc)
dfs_tr(v);
vector<int> vec;
vec.insert(vec.end(), cyce.begin()+1, cyce.end());
vec.insert(vec.end(), gold.begin(), gold.end());
vec.insert(vec.end(), cur.begin(), cur.end());
//cout << cyce[0] << ' ';
//for (int x : vec)
// cout << x << ' ';
//cout << '\n';
vector<int> res;
Loop (i,0,cyc.size()) {
res.push_back(count_common_roads(vec));
vec[i] = cyce[i];
}
//for (int x : res)
// cout << x << ' ';
//cout << '\n';
int mn = res[0], mx = res[0];
for (int x : res) {
mn = min(mn, x);
mx = max(mx, x);
}
if (mn == mx) {
for (int e : cyce)
rem[e] = 1;
return;
}
Loop (i,0,cyc.size()) {
if (res[i] < mx) {
gold.push_back(cyce[i]);
dsu::unite(cyc[i], cyc[i+1 == cyc.size()? 0: i+1]);
} else {
rem[cyce[i]] = 1;
}
}
}
std::vector<int> find_roads(int n, std::vector<int> V, std::vector<int> U)
{
::n = n;
dsu::init();
Loop (i,0,V.size()) {
int v = V[i], u = U[i];
A[v].push_back({u,i});
A[u].push_back({v,i});
Abs[v][u] = 1;
Abs[u][v] = 1;
Am[v][u] = i;
Am[u][v] = i;
}
for (;;) {
memset(par, -1, sizeof(par));
if (!dfscyc(rt(0), -2, -2))
break;
test_cyc();
}
Loop (i,0,V.size()) {
int v = V[i], u = U[i];
if (rem[i] || rt(v) == rt(u))
continue;
gold.push_back(i);
}
return gold;
}
Compilation message
simurgh.cpp: In function 'bool dfscyc(int, int, int)':
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
simurgh.cpp:60:2: note: in expansion of macro 'Loop'
60 | Loop (i,0,A[v].size()) {
| ^~~~
simurgh.cpp: In function 'void test_cyc()':
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
simurgh.cpp:122:2: note: in expansion of macro 'Loop'
122 | Loop (i,0,cyc.size()) {
| ^~~~
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
simurgh.cpp:139:2: note: in expansion of macro 'Loop'
139 | Loop (i,0,cyc.size()) {
| ^~~~
simurgh.cpp:142:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | dsu::unite(cyc[i], cyc[i+1 == cyc.size()? 0: i+1]);
| ~~~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
simurgh.cpp:153:2: note: in expansion of macro 'Loop'
153 | Loop (i,0,V.size()) {
| ^~~~
simurgh.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
simurgh.cpp:168:2: note: in expansion of macro 'Loop'
168 | Loop (i,0,V.size()) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Execution timed out |
3052 ms |
340 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
