제출 #1273028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273028		goulthen	Rigged Roads (NOI19_riggedroads)	C++20	8 / 100	2 ms	576 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

const int MAXN = 1e3+10;
const int INF = 1e18+10;
vector<int> g[MAXN];
int u[MAXN], v[MAXN], tin[MAXN], tout[MAXN], val[MAXN];
int spa[MAXN];
bool ispa[MAXN];

int t = 0;
void dfs(int u, int p = -1) {
	tin[u] = ++t;
	for (int &v : g[u]) if (v!=p) dfs(v,u);
	tout[u] = ++t;
}

bool chd(int u, int v) {
	// v child of u
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int n,m; cin >> n >> m;
	rep(i,1,m) cin >> u[i] >> v[i];
	
	rep(i,1,n-1) {
		int c;cin >> c;
		spa[i] = c;
		ispa[c] = 1;
		int x = u[c], y=v[c];
		g[x].pb(y);
		g[y].pb(x);
	}

	dfs(1);

	int cur = 0;
	rep(i,1,m) {
		if(val[i]) continue;
		if(ispa[i]) {
			val[i] = ++cur;
			continue;
		}
		vector<int> vc;

		rep(j,1,n-1) {
			if (((chd(u[spa[j]],u[i]) && chd(v[spa[j]],u[i])) || (chd(u[spa[j]],v[i]) && chd(v[spa[j]],v[i]))) && !val[spa[j]]) vc.pb(spa[j]);
		}
		sort(vc.begin(), vc.end());

		for (int &x : vc) val[x] = ++cur;
		val[i] = ++cur;
	}

	rep(i,1,m) cout << val[i] << " \n"[i==m];
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 9
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 32