| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55745 |
2018-07-09T00:23:27 Z |
Benq |
Simurgh (IOI17_simurgh) |
C++14 |
|
315 ms |
15552 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
#include "simurgh.h"
int N;
vi U, V;
/*int sec[500*499/2];
int co;
template<int SZ> struct DSU {
int par[SZ], sz[SZ];
DSU() {
F0R(i,SZ) par[i] = i, sz[i] = 1;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y], par[y] = x;
return 1;
}
};
int count_common_roads(vi z) {
co ++;
assert(sz(z) == N-1);
DSU<500> D = DSU<500>();
int ret = 0;
for (int i: z) {
if (!D.unite(U[i],V[i])) exit(5);
if (sec[i]) ret ++;
}
return ret;
}*/
//////
set<int> ctree, adj[500];
int totadj[500], label[500][500], adjsz[500];
void addEdge(int x, int y) {
ctree.insert(x), ctree.insert(y);
// cout << "OH " << x << " " << y << "\n";
adj[x].insert(y), adj[y].insert(x);
}
int get(int x, vi y1, vi y2) {
set<int> cur; cur.insert(x);
for (int i: y1) cur.insert(i);
for (int i: y2) cur.insert(i);
vi edge;
F0R(i,sz(y1)) {
edge.pb(label[x][y1[i]]);
edge.pb(label[y1[i]][y2[i]]);
}
F0R(i,N) if (!cur.count(i)) edge.pb(label[x][i]);
return count_common_roads(edge);
}
void search(int x, vi y, int num) {
if (sz(y) == 1) {
addEdge(x,y[0]);
return;
}
int q = sz(y)/2;
vi y1 = vi(y.begin(),y.begin()+q);
vi y2 = vi(y.begin()+q,y.begin()+2*q);
int t1 = get(x,y1,y2);
int t2 = get(x,y2,y1);
if (t1 > t2) {
search(x,y1,(num+t1-t2)/2);
} else if (t1 < t2) {
search(x,y2,(num+t2-t1)/2);
} else {
if (num == 1) search(x,{y.back()},1);
else search(x,y1,num/2);
}
}
vector<int> find_roads(int n, vi u, vi v) {
N = n, U = u, V = v;
F0R(i,sz(u)) label[u[i]][v[i]] = label[v[i]][u[i]] = i;
ctree.insert(0);
F0R(i,n) {
vi t;
F0R(j,n) if (i != j) t.pb(label[i][j]);
adjsz[i] = count_common_roads(t);
}
while (sz(ctree) < n) {
F0R(i,n) if (ctree.count(i) && sz(adj[i]) < adjsz[i]) {
vi y;
F0R(j,n) if (!ctree.count(j)) y.pb(j);
search(i,y,adjsz[i]-sz(adj[i]));
break;
}
//cout << sz(ctree) << "\n";
//exit(0);
}
vi ans;
F0R(i,n) for (int j: adj[i]) if (i < j) ans.pb(label[i][j]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
600 KB |
correct |
| 4 |
Incorrect |
2 ms |
712 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
600 KB |
correct |
| 4 |
Incorrect |
2 ms |
712 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
600 KB |
correct |
| 4 |
Incorrect |
2 ms |
712 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
712 KB |
correct |
| 2 |
Correct |
2 ms |
828 KB |
correct |
| 3 |
Correct |
159 ms |
4108 KB |
correct |
| 4 |
Correct |
250 ms |
6328 KB |
correct |
| 5 |
Correct |
253 ms |
7432 KB |
correct |
| 6 |
Correct |
286 ms |
8352 KB |
correct |
| 7 |
Correct |
249 ms |
9096 KB |
correct |
| 8 |
Correct |
263 ms |
10092 KB |
correct |
| 9 |
Correct |
268 ms |
11084 KB |
correct |
| 10 |
Correct |
315 ms |
11944 KB |
correct |
| 11 |
Correct |
248 ms |
12872 KB |
correct |
| 12 |
Correct |
272 ms |
13816 KB |
correct |
| 13 |
Correct |
2 ms |
13816 KB |
correct |
| 14 |
Correct |
269 ms |
14876 KB |
correct |
| 15 |
Correct |
267 ms |
15552 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
484 KB |
correct |
| 3 |
Correct |
3 ms |
600 KB |
correct |
| 4 |
Incorrect |
2 ms |
712 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
