| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58819 |
2018-07-19T14:38:02 Z |
reality |
Simurgh (IOI17_simurgh) |
C++17 |
|
1360 ms |
20000 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 w[N][N];
int s[N][N];
int f[N];
vi g[N];
int p[N];
int get(int k) {
return k == p[k] ? k : p[k] = get(p[k]);
}
int was[N * N];
vi E;
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;
vi answer;
vi ee;
for (int l = 0;l < n;++l)
p[l] = l;
for (int i = 0;i < m;++i)
if (get(u[i]) != get(v[i])) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
ee.pb(i);
was[i] = 1;
p[get(u[i])] = get(v[i]);
}
//cerr << "chosed\n";
//for (auto it : ee)
// cerr << "(" << u[it] << ',' << v[it] << ")\n";
//cerr << "end chosed\n";
for (int i = 0;i < m;++i)
if (!was[i]) {
queue < int > Q;
Q.push(u[i]);
for (int j = 0;j < n;++j)
f[j] = -1;
f[u[i]] = u[i];
while (!Q.empty() && f[v[i]] == -1) {
int node = Q.front();
Q.pop();
for (auto it : g[node])
if (f[it] == -1)
f[it] = node,Q.push(it);
}
vi E;
for (int j = v[i];j != u[i];j = f[j])
E.pb(w[j][f[j]]);
int ok = 0;
vi ed;
for (auto it : ee)
ed.pb(it);
ed.pb(i);
for (auto it : E)
ok |= was[it] == 1;
//dbg(i);
//dbg(ok);
if (ok) {
E.pb(i);
//dbg(E.size());
//for (auto it : E)
// cerr << u[it] << ' ' << v[it] << '\n';
//cerr << "end E\n";
int index = -1;
for (int i = 0;i < E.size();++i)
if (was[E[i]] == 3)
index = E[i];
int ind = -1;
for (int i = 0;i < E.size();++i)
if (was[E[i]] == 2)
ind = E[i];
//dbg(index);
//dbg(ind);
vector < pii > rs;
if (index != -1) {
vi e;
for (auto it : ed)
if (it != index)
e.pb(it);
rs.pb(mp(count_common_roads(e),index));
}
if (ind != -1) {
vi e;
for (auto it : ed)
if (it != ind)
e.pb(it);
rs.pb(mp(count_common_roads(e),ind));
}
for (auto a : E)
if (was[a] <= 1) {
vi e;
for (auto it : ed)
if (it != a)
e.pb(it);
rs.pb(mp(count_common_roads(e),a));
}
int mn = min_element(all(rs))->fi;
int mx = max_element(all(rs))->fi;
if (mn == mx) {
for (auto it : rs)
if (was[it.se] == 1)
was[it.se] = 3;
} else {
for (auto it : rs)
if (was[it.se] == 1 && it.fi == mn)
was[it.se] = 2;
else
if (was[it.se] == 1 && it.fi != mn)
was[it.se] = 3;
}
}
}
for (auto it : ee)
s[u[it]][v[it]] = s[v[it]][u[it]] = (was[it] != 3);
for (int i = 0;i < n;++i) {
int deg = 0;
vi e;
int cnt1 = 0;
for (int l = 0;l < n;++l)
p[l] = l;
for (int j = 0;j < n;++j)
if (i != j && w[i][j] != -1)
e.pb(w[i][j]),cnt1 += s[i][j] == 1,p[get(i)] = get(j);
for (auto it : ee)
if (get(u[it]) != get(v[it])) {
p[get(u[it])] = get(v[it]);
e.pb(it);
}
int cnt2 = count_common_roads(e);
deg = cnt2 - cnt1;
vi mk;
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 && w[i][j] != -1)
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;
}
mk.pb(t);
}
for (auto it : mk)
s[it][i] = s[i][it] = 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:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0;i < E.size();++i)
~~^~~~~~~~~~
simurgh.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0;i < E.size();++i)
~~^~~~~~~~~~
simurgh.cpp:32: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 |
8 ms |
8568 KB |
correct |
| 3 |
Correct |
9 ms |
8752 KB |
correct |
| 4 |
Incorrect |
10 ms |
8752 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
8 ms |
8568 KB |
correct |
| 3 |
Correct |
9 ms |
8752 KB |
correct |
| 4 |
Incorrect |
10 ms |
8752 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
8 ms |
8568 KB |
correct |
| 3 |
Correct |
9 ms |
8752 KB |
correct |
| 4 |
Incorrect |
10 ms |
8752 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8752 KB |
correct |
| 2 |
Correct |
9 ms |
8752 KB |
correct |
| 3 |
Correct |
697 ms |
10148 KB |
correct |
| 4 |
Correct |
1218 ms |
10820 KB |
correct |
| 5 |
Correct |
1121 ms |
11436 KB |
correct |
| 6 |
Correct |
1239 ms |
12324 KB |
correct |
| 7 |
Correct |
1215 ms |
13340 KB |
correct |
| 8 |
Correct |
1360 ms |
14304 KB |
correct |
| 9 |
Correct |
1146 ms |
15304 KB |
correct |
| 10 |
Correct |
1267 ms |
16160 KB |
correct |
| 11 |
Correct |
1245 ms |
16960 KB |
correct |
| 12 |
Correct |
1215 ms |
18016 KB |
correct |
| 13 |
Correct |
10 ms |
18016 KB |
correct |
| 14 |
Correct |
1316 ms |
18984 KB |
correct |
| 15 |
Correct |
1211 ms |
20000 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8568 KB |
correct |
| 2 |
Correct |
8 ms |
8568 KB |
correct |
| 3 |
Correct |
9 ms |
8752 KB |
correct |
| 4 |
Incorrect |
10 ms |
8752 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
