| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58797 |
2018-07-19T13:17:00 Z |
reality |
Simurgh (IOI17_simurgh) |
C++17 |
|
13 ms |
8844 KB |
#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1024;
int was[N * N];
int w[N][N];
int s[N][N];
int f[N];
vi g[N];
pii dfs(int node) {
for (auto it : g[node])
if (f[it] == -1 && !was[w[node][it]]) {
f[it] = node;
auto cnt = dfs(it);
if (cnt != mp(-1,-1))
return cnt;
}
else
if (f[node] != it && f[it] != -1 && !was[w[node][it]])
return mp(node,it);
return mp(-1,-1);
}
int p[N];
int Ws[N * N];
int get(int k) {
return k == p[k] ? k : p[k] = get(p[k]);
}
vi find_roads(int n,vi u,vi v) {
if (n == 2) {
return vi{0};
}
int called = 0;
int m = u.size();
memset(w,-1,sizeof(w));
memset(s,-1,sizeof(s));
for (int i = 0;i < m;++i)
w[u[i]][v[i]] = w[v[i]][u[i]] = i,g[u[i]].pb(v[i]),g[v[i]].pb(u[i]);
vi answer;
if (m != n * (n - 1) / 2) {
for (int i = 0;i < n;++i)
p[i] = i;
vi ee;
for (int i = 0;i < m;++i)
if (get(u[i]) != get(v[i])) {
ee.pb(i);
p[get(u[i])] = get(v[i]);
}
do {
vi cycle;
for (int i = 0;i < n;++i)
f[i] = -1;
f[0] = 0;
auto cnt = dfs(0);
if (cnt != mp(-1,-1)) {
cycle.pb(w[cnt.fi][cnt.se]);
for (int i = cnt.fi;i != cnt.se;i = f[i])
cycle.pb(w[i][f[i]]);
} else {
int ok = 1;
for (int i = 0;i < m;++i)
if (Ws[i])
ok &= !was[i];
if (ok)
break;
else {
for (int i = 0;i < m;++i)
if (Ws[i])
was[i] = 0;
}
}
for (auto it : cycle)
was[it] = 1;
vector < pii > rs;
int shit = 0;
for (int i = 0;i < cycle.size();++i) {
if (Ws[cycle[i]]) {
++shit;
if (shit > 1)
continue;
}
for (int j = 0;j < n;++j)
p[j] = j;
vi e;
for (int j = 0;j < cycle.size();++j)
if (i != j) {
p[get(u[cycle[j]])] = get(v[cycle[j]]);
e.pb(cycle[j]);
}
for (auto it : ee)
if (get(u[it]) != get(v[it])) {
e.pb(it);
p[get(u[it])] = get(v[it]);
}
rs.pb(mp(count_common_roads(e),cycle[i]));
}
int mn = min_element(all(rs))->fi;
int mx = max_element(all(rs))->fi;
if (mn != mx) {
for (auto it : rs)
if (it.fi == mn)
Ws[it.se] = 1;
}
} while (1);
for (int i = 0;i < m;++i)
if (Ws[i] || (!Ws[i] && !was[i]))
answer.pb(i);
} else {
vi ee;
for (int i = 0;i + 1 < n;++i)
ee.pb(w[i][i + 1]);
for (int i = 0;i + 1 < n;++i) {
vi e1,e2,e3;
int nxt = 0;
while (nxt == i || nxt == i + 1)
(++nxt) %= n;
for (int j = 0;j < n;++j)
if (j != i && j != i + 1 && j != nxt)
e1.pb(w[j][(j + 1) % n]);
e3 = e2 = e1;
e1.pb(w[nxt][i]);
e1.pb(w[i][i + 1]);
e2.pb(w[i][i + 1]);
e2.pb(w[i + 1][nxt]);
e3.pb(w[i + 1][nxt]);
e3.pb(w[nxt][i]);
int cnt1 = count_common_roads(e1);
int cnt2 = count_common_roads(e2);
int cnt3 = count_common_roads(e3);
if (min({cnt1,cnt2,cnt3}) != max({cnt1,cnt2,cnt3})) {
if (cnt3 <= cnt1 && cnt3 <= cnt2)
s[i][i + 1] = s[i + 1][i] = 1;
else
s[i][i + 1] = s[i + 1][i] = 0;
} else
s[i][i + 1] = s[i + 1][i] = 0;
}
for (int i = 0;i < n;++i) {
int deg = 0;
vi e;
int cnt1 = 0;
for (int j = 0;j < n;++j)
if (i != j)
e.pb(w[i][j]),cnt1 += s[i][j] == 1;
int cnt2 = count_common_roads(e);
deg = cnt2 - cnt1;
for (int k = 1;k <= deg;++k) {
int t = 0;
for (int d = 1 << 9;d;d /= 2)
if (t + d < n) {
vi e;
for (int l = 0;l < n;++l)
p[l] = l;
int cnt1 = 0;
for (int j = 0;j < t + d;++j)
if (j != i)
e.pb(w[i][j]),cnt1 += s[i][j] == 1,p[get(j)] = get(i);
for (auto it : ee)
if (get(u[it]) != get(v[it])) {
cnt1 += s[u[it]][v[it]];
p[get(u[it])] = get(v[it]);
e.pb(it);
}
int cnt2 = count_common_roads(e);
if (cnt2 - cnt1 < k)
t += d;
}
s[i][t] = s[t][i] = 1;
}
}
for (int i = 0;i < n;++i)
for (int j = 0;j < i;++j)
if (s[i][j] == 1)
answer.pb(w[i][j]);
}
return answer;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0;i < cycle.size();++i) {
~~^~~~~~~~~~~~~~
simurgh.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0;j < cycle.size();++j)
~~^~~~~~~~~~~~~~
simurgh.cpp:45:6: warning: unused variable 'called' [-Wunused-variable]
int called = 0;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
13 ms |
8732 KB |
correct |
| 3 |
Incorrect |
10 ms |
8744 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
13 ms |
8732 KB |
correct |
| 3 |
Incorrect |
10 ms |
8744 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
13 ms |
8732 KB |
correct |
| 3 |
Incorrect |
10 ms |
8744 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8744 KB |
correct |
| 2 |
Incorrect |
9 ms |
8844 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
13 ms |
8732 KB |
correct |
| 3 |
Incorrect |
10 ms |
8744 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
