oj.uz

Submission #935999

# Submission time Handle Problem Language Result Execution time Memory
935999 2024-02-29T22:16:44 Z Litusiano Railway (BOI17_railway) C++17
36 / 100
 227 ms 58312 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);
	if(u != 1) 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 348 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 348 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 211 ms 58312 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 180 ms 57676 KB Output is correct
4 Correct 194 ms 57444 KB Output is correct
5 Correct 212 ms 56916 KB Output is correct
6 Correct 152 ms 56552 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 51848 KB Output is correct
2 Correct 202 ms 49784 KB Output is correct
3 Correct 211 ms 55444 KB Output is correct
4 Correct 204 ms 55500 KB Output is correct
5 Correct 227 ms 55752 KB Output is correct
6 Correct 157 ms 52008 KB Output is correct
7 Correct 152 ms 51916 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 51848 KB Output is correct
2 Correct 202 ms 49784 KB Output is correct
3 Correct 211 ms 55444 KB Output is correct
4 Correct 204 ms 55500 KB Output is correct
5 Correct 227 ms 55752 KB Output is correct
6 Correct 157 ms 52008 KB Output is correct
7 Correct 152 ms 51916 KB Output is correct
8 Correct 188 ms 52104 KB Output is correct
9 Correct 168 ms 52176 KB Output is correct
10 Correct 168 ms 56524 KB Output is correct
11 Correct 156 ms 56776 KB Output is correct
12 Incorrect 149 ms 49336 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -