Submission #1070889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070889		TAhmed33	Rigged Roads (NOI19_riggedroads)	C++98	49 / 100	2080 ms	108220 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 25;
int n, m;
set <int> vis;
vector <int> cc[MAXN];
int val[MAXN];
int ee[MAXN][2];	
map <int, int> ind[MAXN];
bool good[MAXN];
vector <int> cur, dd;
void dfs (int pos, int par, int d) {
	cur.push_back(pos);
	if (pos == d) {
		dd = cur;
	}
	for (auto j : cc[pos]) {
		if (j != par) {
			dfs(j, pos, d);
		}
	}
	cur.pop_back();
}
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		vis.insert(i);
	}
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b;
		ee[i][0] = a; ee[i][1] = b;
		ind[a][b] = ind[b][a] = i;
	}

	for (int i = 1; i < n; i++) {
		int x; cin >> x; good[x] = 1;
		cc[ee[x][0]].push_back(ee[x][1]);
		cc[ee[x][1]].push_back(ee[x][0]);
	}
	for (int i = 1; i <= m; i++) {
		if (val[i]) {
			continue;
		}
		if (good[i]) {
			val[i] = *(vis.begin());
			vis.erase(val[i]);
			continue;	
		}
		dfs(ee[i][0], -1, ee[i][1]);
		vector <int> g;
		for (int j = 0; j + 1 < (int)dd.size(); j++) {
			g.push_back(ind[dd[j]][dd[j + 1]]);
		}
		sort(g.begin(), g.end());
		for (auto j : g) {
			if (val[j]) {
				continue;
			}
			val[j] = *(vis.begin());
			vis.erase(val[j]);
		}
		val[i] = *(vis.begin());
		vis.erase(val[i]);
	}
	for (int i = 1; i <= m; i++) {
		cout << val[i] << '\n';
	}
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

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