oj.uz

Submission #877240

# Submission time Handle Problem Language Result Execution time Memory
877240 2023-11-23T04:41:54 Z wii Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 366 ms 110520 KB 
#include <bits/stdc++.h>
using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;

#define int ll
typedef pair<int, int> pii;

#define lx (id << 1)
#define rx (lx | 1)
#define gcd __gcd
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

const ll Linf = 0x3f3f3f3f3f3f3f3f;
const int Inf = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const ll Mod2 = ll(1e9) + 9;
const int Lim = 1e6 + 5;
const int inv6 = 166666668;

// #define Sieve
#ifdef Sieve
    vector<int> pr;
    vector<int> lpf;
    void Linear_sieve(int n = Lim) {
        pr.assign(1, 2);
        lpf.assign(n + 1, 2);

        for (int x = 3; x <= n; x += 2) {
            if (lpf[x] == 2) pr.push_back(lpf[x] = x);
            for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
                lpf[pr[i] * x] = pr[i];
        }
    }
#endif

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

const int base = 3;
const int N = 3e5 + 5;
const int K = log2(N) + 1;
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};
const int block_size = sqrt(2e9) + 2;

int n, m;
int a[N];
vector<pair<int, int>> edges;

vector<pii> adj[N];
int up[N][K + 1], dep[N], par[N];
int tin[N], tout[N], timer;

struct Dsu {
	int par[N];

	Dsu() {
		memset(par, 0, sizeof par);
	}

	int root(int u) {
		return par[u] == 0 ? u : par[u] = root(par[u]);
	}

	int join(int u, int v) {
		if ((u = root(u)) == (v = root(v)))
			return false;
		
		if (dep[u] > dep[v]) swap(u, v);
		
		par[v] = u; return true;
	}

	int ok(int u, int v) {
		return root(u) != root(v);
	}
};	

void dfs(int u, int p) {
	tin[u] = ++timer;

	dep[u] = dep[p] + 1; 
	up[u][0] = p;
	foru(k, 1, K)
		up[u][k] = up[up[u][k - 1]][k - 1];

	for (auto [v, id]: adj[u]) if (v != p) {
		par[v] = id;
		dfs(v, u);
	}

	tout[u] = timer;
}

int isanc(int u, int v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
	if (isanc(u, v)) return u;
	if (isanc(v, u)) return v;

	ford(k, K, 0) if (up[u][k])
		if (!isanc(up[u][k], v))
			u = up[u][k];
	return up[u][0];
}

int dist(int u, int v) {
	return dep[u] + dep[v] - 2*dep[lca(u, v)];
}

int ans[N], top;
void solve() {
    cin >> n >> m;
	foru(i, 1, m) {
		int u, v;
		cin >> u >> v;
		edges.emplace_back(u, v);
	} 

	foru(i, 1, n - 1) {
		int x; cin >> x; --x; 

		int u = edges[x].first, v = edges[x].second;
		
		adj[u].emplace_back(v, x);
		adj[v].emplace_back(u, x);

		a[x] = true;
	}

	dfs(1, 0);

	Dsu St;
	for (int i = 0; i < m; ++i) if (ans[i] == 0) {
		int u = edges[i].first;
		int v = edges[i].second;

		int w = lca(u, v);

		static vector<int> f;
		if (!f.empty()) f.clear();

		for (int x = St.root(u); dep[x] > dep[w]; x = St.root(u)) {
			int id = par[x];
			int p = up[x][0];

			f.push_back(id);

			St.join(x, p);
		}

		for (int x = St.root(v); dep[x] > dep[w]; x = St.root(v)) {
			int id = par[x];
			int p = up[x][0];

			f.push_back(id);

			St.join(x, p);
		}

		sort(all(f));
		for (int &id: f) {
			ans[id] = ++top;
		}

		if (ans[i] == 0) ans[i] = ++top;
	}

	for (int i = 0; i < m; ++i)
		cout << ans[i] << " \n"[i == m];
}

signed main() {
    FastIO;

    #define task ""
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    #define task "test"
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    #ifdef Sieve
        Linear_sieve();
    #endif

    int ntest = 1;
    // cin >> ntest;
    while (ntest--) {
        //cout << "Case " << q << ": " << "\n"; 
        solve();
        cout << "\n";
    }

    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

riggedroads.cpp:195: warning: "task" redefined
  195 |     #define task "test"
      | 
riggedroads.cpp:189: note: this is the location of the previous definition
  189 |     #define task ""
      | 
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:191:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:192:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:197:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:198:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 5 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 5 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 5 ms 17244 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 5 ms 17244 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct
8 Correct 4 ms 17180 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47656 KB Output is correct
2 Correct 83 ms 56768 KB Output is correct
3 Correct 68 ms 37560 KB Output is correct
4 Correct 149 ms 96100 KB Output is correct
5 Correct 147 ms 101560 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 55724 KB Output is correct
2 Correct 46 ms 36168 KB Output is correct
3 Correct 24 ms 29852 KB Output is correct
4 Correct 54 ms 46928 KB Output is correct
5 Correct 22 ms 32748 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 93800 KB Output is correct
2 Correct 221 ms 103336 KB Output is correct
3 Correct 50 ms 45000 KB Output is correct
4 Correct 75 ms 54864 KB Output is correct
5 Correct 292 ms 110520 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 71208 KB Output is correct
2 Correct 121 ms 53816 KB Output is correct
3 Correct 349 ms 98544 KB Output is correct
4 Correct 346 ms 92228 KB Output is correct
5 Correct 19 ms 28372 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16988 KB Output is correct
2 Correct 5 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 5 ms 17244 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 5 ms 17244 KB Output is correct
7 Correct 4 ms 17244 KB Output is correct
8 Correct 4 ms 17180 KB Output is correct
9 Correct 51 ms 47656 KB Output is correct
10 Correct 83 ms 56768 KB Output is correct
11 Correct 68 ms 37560 KB Output is correct
12 Correct 149 ms 96100 KB Output is correct
13 Correct 147 ms 101560 KB Output is correct
14 Correct 79 ms 55724 KB Output is correct
15 Correct 46 ms 36168 KB Output is correct
16 Correct 24 ms 29852 KB Output is correct
17 Correct 54 ms 46928 KB Output is correct
18 Correct 22 ms 32748 KB Output is correct
19 Correct 198 ms 93800 KB Output is correct
20 Correct 221 ms 103336 KB Output is correct
21 Correct 50 ms 45000 KB Output is correct
22 Correct 75 ms 54864 KB Output is correct
23 Correct 292 ms 110520 KB Output is correct
24 Correct 182 ms 71208 KB Output is correct
25 Correct 121 ms 53816 KB Output is correct
26 Correct 349 ms 98544 KB Output is correct
27 Correct 346 ms 92228 KB Output is correct
28 Correct 19 ms 28372 KB Output is correct
29 Correct 358 ms 90616 KB Output is correct
30 Correct 366 ms 96208 KB Output is correct
31 Correct 324 ms 96884 KB Output is correct
32 Correct 85 ms 36112 KB Output is correct
33 Correct 345 ms 96132 KB Output is correct