| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 49983 | Benq | Simurgh (IOI17_simurgh) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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"
vpi adj[500];
int comp[500];
vi tre[500], tmp[500], allComp;
int n;
int need[500*499/2], sec[500*499/2];
vi u,v, res;
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 co = 0;
/*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;
}*/
void test(int ind) {
vpi bes;
for (int x: tmp[ind]) {
vi z = {x};
for (int i: allComp) {
if (i != ind && i > 0) z.pb(tmp[i].back());
z.insert(z.end(),all(tre[i]));
}
bes.pb({count_common_roads(z),x});
}
sort(all(bes));
for (auto a: bes) {
if (a.f == bes.back().f) {
// cout << "ZZ " << a.s << " " << sz(bes) << "\n";
need[a.s] = 1;
res.pb(a.s);
} else need[a.s] = -1;
}
}
void dfs(int x, int lab) {
comp[x] = lab;
for (auto a: adj[x]) if (comp[a.f] == -1) {
tre[lab].pb(a.s);
dfs(a.f,lab);
}
}
void test() {
res.clear();
FOR(i,1,n) {
tre[i].clear();
tmp[i].clear();
}
allComp.clear();
allComp.pb(0);
F0R(i,n) if (comp[i] == -1) {
allComp.pb(i);
dfs(i,i);
}
F0R(i,n) if (comp[i] != 0)
for (auto a: adj[i]) if (need[a.s] == 0 && comp[a.f] == 0) {
//cout << "HUH " << i << " " << a.f << " " << a.s << "\n";
tmp[comp[i]].pb(a.s);
}
for (int i: allComp) if (i) test(i);
for (int i: res) tre[0].pb(i);
}
vector<int> find_roads(int N, vi U, vi V) {
n = N, u = U, v = V;
// for (int i: v) cout << i << " ";
//cout << ""
F0R(i,sz(u)) {
adj[u[i]].pb({v[i],i});
adj[v[i]].pb({u[i],i});
//cout << "OH " << u[i] << " " << v[i] << " " << i << "\n";
}
FOR(i,1,n) comp[i] = -1;
while (1) {
for (int i: tre[0]) comp[u[i]] = comp[v[i]] = 0;
int lef = 0;
F0R(i,n) if (comp[i] != 0) {
comp[i] = -1;
lef ++;
}
if (lef == 0) break;
test();
}
vi ans;
F0R(i,sz(u)) if (need[i] == 1) ans.pb(i);
// cout << co << "\n";
return ans;
}