oj.uz

Submission #1070889

# Submission time Handle Problem Language Result Execution time Memory
1070889 2024-08-22T20:26:03 Z TAhmed33 Rigged Roads (NOI19_riggedroads) C++
49 / 100
 2000 ms 108220 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23132 KB Output is correct
2 Correct 4 ms 23160 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23132 KB Output is correct
2 Correct 4 ms 23160 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 6 ms 23388 KB Output is correct
5 Correct 7 ms 23388 KB Output is correct
6 Correct 10 ms 23388 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 44756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 60932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 91764 KB Output is correct
2 Correct 259 ms 96856 KB Output is correct
3 Correct 86 ms 45652 KB Output is correct
4 Correct 98 ms 55632 KB Output is correct
5 Correct 311 ms 108220 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 62756 KB Output is correct
2 Correct 119 ms 52680 KB Output is correct
3 Correct 353 ms 87540 KB Output is correct
4 Correct 313 ms 80720 KB Output is correct
5 Correct 24 ms 30296 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23132 KB Output is correct
2 Correct 4 ms 23160 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 6 ms 23388 KB Output is correct
5 Correct 7 ms 23388 KB Output is correct
6 Correct 10 ms 23388 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 5 ms 23132 KB Output is correct
9 Execution timed out 2061 ms 44756 KB Time limit exceeded
10 Halted 0 ms 0 KB -