oj.uz

Submission #205778

# Submission time Handle Problem Language Result Execution time Memory
205778 2020-02-29T20:55:36 Z ly20 Railway (BOI17_railway) C++17
0 / 100
 1000 ms 33940 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 20;
int dp[MAXN][MAXK], prof[MAXN];
vector <int> grafo[MAXN];
void dfs(int v, int p) {
	dp[v][0] = p;
	for(int i = 1; i < MAXK; i++) {
		dp[v][i] = dp[dp[v][i - 1]][i - 1];
	}
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		if(viz == p) continue;
		prof[viz] = prof[v] + 1;
		dfs(viz, v);
	}
}
int lca(int a, int b) {
	if(prof[a] > prof[b]) swap(a, b);
	int d = prof[b] - prof[a];
	for(int i = 0; i < MAXK; i++) {
		if(d & (1 << i)) b = dp[b][i];
	}
	if(a == b) return a;
	for(int i = MAXK - 1; i >= 0; i--) {
		if(dp[a][i] != dp[b][i]) {
			a = dp[a][i]; b = dp[b][i];
		}
	}
	return dp[a][0];
}
map < pair < int, int >, int > mp;
set < int > s;
set < int > :: iterator it; 
int marc[MAXN], cont[MAXN];
bool dfs1(int v, int p) {
	//printf("%d\n", v);
	bool ok = false;
	if(marc[v] == 1) ok = true;
	for(int i = 0; i < grafo[v].size(); i++) {
		int viz = grafo[v][i];
		//printf("%d %d\n", v, viz);
		if(viz == p) continue;
		//printf("oi\n");
		if(dfs1(viz, v)) ok = true;
	}
	if(ok) {
		cont[v]++;
		//printf("%d++\n", v);
	}
	return ok;
}
int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		grafo[a].push_back(b); grafo[b].push_back(a);
		mp[make_pair(a, b)] = i; mp[make_pair(b, a)] = i;
	}
	dfs(1, 1);
	for(int i = 0; i < m; i++) {
		vector < int > v;
		int a;
		scanf("%d", &a);
		int lc;
		scanf("%d", &lc);
		v.push_back(lc);
		marc[lc] = 1;
		for(int j = 1; j < a; j++) {
			int b;
			scanf("%d", &b);
			marc[b] = 1;
			v.push_back(b);
			lc = lca(lc, b);
		}
		//printf("%d\n", lc);
		dfs1(lc, lc);
		cont[lc]--;
		for(int j = 0; j < a; j++) {
			marc[v[j]] = 0;
		}
		v.clear();
	}
	vector <int> v;
	for(int i = 1; i <= n; i++) {
		if(cont[i] >= k) v.push_back(mp[make_pair(i, dp[i][0])]);
	}
	printf("%d\n", v.size());
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size() - 1; i++) printf("%d ", v[i]);
	printf("%d\n", v[v.size() - 1]);
	return 0;
}

Compilation message

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'bool dfs1(int, int)':
railway.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:90:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", v.size());
                 ~~~~~~~~^
railway.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size() - 1; i++) printf("%d ", v[i]);
                 ~~^~~~~~~~~~~~~~
railway.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
railway.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &lc);
   ~~~~~^~~~~~~~~~~
railway.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 67 ms 5496 KB Output is correct
3 Correct 70 ms 5368 KB Output is correct
4 Correct 6 ms 2936 KB Output is correct
5 Correct 6 ms 2936 KB Output is correct
6 Correct 100 ms 5752 KB Output is correct
7 Correct 42 ms 5496 KB Output is correct
8 Correct 97 ms 5540 KB Output is correct
9 Runtime error 116 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 67 ms 5496 KB Output is correct
3 Correct 70 ms 5368 KB Output is correct
4 Correct 6 ms 2936 KB Output is correct
5 Correct 6 ms 2936 KB Output is correct
6 Correct 100 ms 5752 KB Output is correct
7 Correct 42 ms 5496 KB Output is correct
8 Correct 97 ms 5540 KB Output is correct
9 Runtime error 116 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 67 ms 5496 KB Output is correct
3 Correct 70 ms 5368 KB Output is correct
4 Correct 6 ms 2936 KB Output is correct
5 Correct 6 ms 2936 KB Output is correct
6 Correct 100 ms 5752 KB Output is correct
7 Correct 42 ms 5496 KB Output is correct
8 Correct 97 ms 5540 KB Output is correct
9 Runtime error 116 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -