oj.uz

Submission #382246

# Submission time Handle Problem Language Result Execution time Memory
382246 2021-03-26T20:04:02 Z Return_0 Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 1295 ms 93028 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 3e5 + 7, lg = 19;

// struct myHash { ll operator () (pll x) const { return 101 * x.fr + x.sc; } };

ll P [N], par [N], anc [N][lg], h [N], lst, n, m;
pll E [N];
// gp_hash_table <pll, ll, myHash> mp;
map <pll, ll> mp;
vector <ll> adj [N], vec;

void dfs (cl &v = 1, cl &pr = 1) {
	h[v] = h[pr] + 1;
	anc[v][0] = pr;
	for (ll i = 1; i < lg; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
	for (auto &u : adj[v]) if (u != pr) dfs(u, v);
}

inline ll up (ll v, cl &d) { for (ll i = lg; i--;) if (d >> i & 1) v = anc[v][i]; return v; }
inline ll LCA (ll v, ll u) {
	if (h[v] > h[u]) swap(v, u);
	u = up(u, h[u] - h[v]);
	if (v == u) return v;
	for (ll i = lg; i--;) if (anc[v][i] ^ anc[u][i]) v = anc[v][i], u = anc[u][i];
	return anc[v][0];
}

ll getpar (cl &v) { return par[v] = (par[v] == v ? v : getpar(par[v])); }

void ok (ll v, ll u) {
	ll lca = LCA(v, u);
	vec.clear();

	for (v = getpar(v); h[lca] < h[v]; v = par[v]) {
		vec.push_back(mp[{v, anc[v][0]}]);
		par[v] = getpar(anc[v][0]);
	}

	for (u = getpar(u); h[lca] < h[u]; u = par[u]) {
		vec.push_back(mp[{u, anc[u][0]}]);
		par[u] = getpar(anc[u][0]);
	}

	sort(All(vec));
	for (auto &x : vec) P[x] = ++lst;
}
inline void fuck (pll &x) { if (h[x.fr] > h[x.sc]) swap(x.fr, x.sc); par[x.sc] = getpar(x.fr); }

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	iota(par, par + N, 0);
	cin>> n >> m;
	for (ll i = 1; i <= m; i++) cin>> E[i].fr >> E[i].sc;
	for (ll i = 1, x; i < n; i++) {
		cin>> x;
		mp[E[x]] = mp[{E[x].sc, E[x].fr}] = x;
		adj[E[x].fr].push_back(E[x].sc);
		adj[E[x].sc].push_back(E[x].fr);
	}

	dfs();

	for (ll i = 1; i <= m; i++) if (!P[i]) {
		if (mp.find(E[i]) == mp.end()) ok(E[i].fr, E[i].sc);
		else fuck(E[i]);
		P[i] = ++lst;
	}

	output(1, m, P, 1);

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
4 5
3 4
1 2
2 3
1 3
1 4
2 4 5

4 4
1 2
1 4
2 3
3 4
1 3 4

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8556 KB Output is correct
2 Correct 7 ms 8556 KB Output is correct
3 Correct 7 ms 8556 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8556 KB Output is correct
2 Correct 7 ms 8556 KB Output is correct
3 Correct 7 ms 8556 KB Output is correct
4 Correct 7 ms 8812 KB Output is correct
5 Correct 8 ms 8812 KB Output is correct
6 Correct 8 ms 8832 KB Output is correct
7 Correct 8 ms 8684 KB Output is correct
8 Correct 7 ms 8812 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 34020 KB Output is correct
2 Correct 337 ms 44900 KB Output is correct
3 Correct 194 ms 21484 KB Output is correct
4 Correct 615 ms 82524 KB Output is correct
5 Correct 674 ms 85992 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 41064 KB Output is correct
2 Correct 142 ms 20844 KB Output is correct
3 Correct 63 ms 15212 KB Output is correct
4 Correct 162 ms 32548 KB Output is correct
5 Correct 60 ms 18668 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 77136 KB Output is correct
2 Correct 727 ms 84836 KB Output is correct
3 Correct 163 ms 30448 KB Output is correct
4 Correct 270 ms 41196 KB Output is correct
5 Correct 829 ms 93028 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 54120 KB Output is correct
2 Correct 395 ms 40044 KB Output is correct
3 Correct 1292 ms 81900 KB Output is correct
4 Correct 1172 ms 77036 KB Output is correct
5 Correct 59 ms 15596 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8556 KB Output is correct
2 Correct 7 ms 8556 KB Output is correct
3 Correct 7 ms 8556 KB Output is correct
4 Correct 7 ms 8812 KB Output is correct
5 Correct 8 ms 8812 KB Output is correct
6 Correct 8 ms 8832 KB Output is correct
7 Correct 8 ms 8684 KB Output is correct
8 Correct 7 ms 8812 KB Output is correct
9 Correct 199 ms 34020 KB Output is correct
10 Correct 337 ms 44900 KB Output is correct
11 Correct 194 ms 21484 KB Output is correct
12 Correct 615 ms 82524 KB Output is correct
13 Correct 674 ms 85992 KB Output is correct
14 Correct 221 ms 41064 KB Output is correct
15 Correct 142 ms 20844 KB Output is correct
16 Correct 63 ms 15212 KB Output is correct
17 Correct 162 ms 32548 KB Output is correct
18 Correct 60 ms 18668 KB Output is correct
19 Correct 628 ms 77136 KB Output is correct
20 Correct 727 ms 84836 KB Output is correct
21 Correct 163 ms 30448 KB Output is correct
22 Correct 270 ms 41196 KB Output is correct
23 Correct 829 ms 93028 KB Output is correct
24 Correct 701 ms 54120 KB Output is correct
25 Correct 395 ms 40044 KB Output is correct
26 Correct 1292 ms 81900 KB Output is correct
27 Correct 1172 ms 77036 KB Output is correct
28 Correct 59 ms 15596 KB Output is correct
29 Correct 1217 ms 77288 KB Output is correct
30 Correct 1295 ms 83304 KB Output is correct
31 Correct 1289 ms 83812 KB Output is correct
32 Correct 254 ms 20972 KB Output is correct
33 Correct 1242 ms 84260 KB Output is correct