oj.uz

Submission #935998

# Submission time Handle Problem Language Result Execution time Memory
935998 2024-02-29T22:10:28 Z Litusiano Railway (BOI17_railway) C++17
36 / 100
 217 ms 60184 KB 
#include<bits/stdc++.h>
using namespace std;

struct LCA{
	int n;
	vector<vector<int>> jump;
	vector<int> dep;
	void dfs(int u, int p, int d, vector<vector<int>>& G, vector<int>& used){
		if(used[u]) return;
		dep[u] = d;
		used[u] = 1;
		jump[u][0] = p;
		for(int v : G[u]) dfs(v,u,d+1,G,used);
	}
	void init(int n1, vector<vector<int>>& G){
		n = n1;
		jump.assign(n+1,vector<int>(25,1));
		dep.assign(n+1,0);
		vector<int> used(n+1,0);
		dfs(1,1,0,G,used);
		for(int k = 1; k<25; k++){
			for(int u = 1; u<=n; u++){
				jump[u][k] = jump[jump[u][k-1]][k-1];
			}
		}
	}
	int LCAA(int a, int b){
		if(dep[a] > dep[b]) swap(a,b);
		int x = dep[b]-dep[a];
		for(int i = 0; i<25; i++){
			if(x & (1<<i)){
				b = jump[b][i];
			}
		}
		if(a == b) return a;
		for(int i = 24; i>=0; i--){
			if(jump[a][i] != jump[b][i]){
				a = jump[a][i];
				b = jump[b][i];
			}
		}
		return jump[a][0];
	}
};

int n,m,k;
vector<vector<int>> G;
vector<vector<int>> isLCA, FromU;
vector<set<int>> SmtoLG;
vector<int> used, fromk;

void dfs(int u){
	if(used[u]) return;
	used[u] = 1;
	for(int v : G[u]){
		if(used[v]) continue;
		dfs(v);
		if(SmtoLG[v].size() > SmtoLG[u].size()) swap(SmtoLG[u], SmtoLG[v]);
		for(auto x : SmtoLG[v]) SmtoLG[u].insert(x);
	}
	for(auto x : FromU[u]) SmtoLG[u].insert(x);
	for(auto x : isLCA[u]) SmtoLG[u].erase(x);
	fromk[u] = SmtoLG[u].size();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>k;
	G.assign(n+1,vector<int>()); isLCA = G; FromU = isLCA;
	map<pair<int,int>,int> edge;
	for(int i = 1; i<n; i++){
		int u,v; cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		pair<int,int> p = {u,v};
		edge[p] = i;
		swap(p.first,p.second);
		edge[p] = i;
	}
	LCA LC; LC.init(n,G);
	for(int i = 0; i<m; i++){
		int x; cin>>x;
		int a,b; cin>>a>>b;
		FromU[a].push_back(i); FromU[b].push_back(i);
		int lc = LC.LCAA(a,b);
		for(int j = 0; j<x-2; j++){
			int c; cin>>c;
			FromU[c].push_back(i);
			lc = LC.LCAA(lc,c);
		}
		isLCA[lc].push_back(i);
	}
	SmtoLG.resize(n+1);
	used.assign(n+1,0); fromk = used;
	dfs(1);
	vector<int> ans;
	for(int i = 1; i<=n; i++){
		//cout<<fromk[i]<<" ";
		if(fromk[i] >= k){
			ans.push_back(edge[{i, LC.jump[i][0]}]);
		}
	}
	cout<<ans.size()<<endl;
	for(int i : ans) cout<<i<<" "; cout<<endl;
}

Compilation message

railway.cpp: In function 'int main()':
railway.cpp:105:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |  for(int i : ans) cout<<i<<" "; cout<<endl;
      |  ^~~
railway.cpp:105:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |  for(int i : ans) cout<<i<<" "; cout<<endl;
      |                                 ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 60184 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 171 ms 59600 KB Output is correct
4 Correct 189 ms 59644 KB Output is correct
5 Correct 166 ms 58576 KB Output is correct
6 Correct 151 ms 58684 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 53556 KB Output is correct
2 Correct 184 ms 51676 KB Output is correct
3 Correct 203 ms 57292 KB Output is correct
4 Correct 201 ms 57184 KB Output is correct
5 Correct 217 ms 57672 KB Output is correct
6 Correct 159 ms 53916 KB Output is correct
7 Correct 166 ms 53708 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 53556 KB Output is correct
2 Correct 184 ms 51676 KB Output is correct
3 Correct 203 ms 57292 KB Output is correct
4 Correct 201 ms 57184 KB Output is correct
5 Correct 217 ms 57672 KB Output is correct
6 Correct 159 ms 53916 KB Output is correct
7 Correct 166 ms 53708 KB Output is correct
8 Correct 166 ms 53940 KB Output is correct
9 Correct 167 ms 53508 KB Output is correct
10 Correct 158 ms 58336 KB Output is correct
11 Correct 151 ms 58088 KB Output is correct
12 Incorrect 130 ms 50656 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -