oj.uz

Submission #936000

# Submission time Handle Problem Language Result Execution time Memory
936000 2024-02-29T22:22:26 Z Litusiano Railway (BOI17_railway) C++17
36 / 100
 207 ms 58348 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 = 2; i<=n; i++){
		//cout<<fromk[i]<<" ";
		if(fromk[i] >= k){
			// cerr<<i<<" "<<LC.jump[i][0]<<endl;
			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:106:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  106 |  for(int i : ans) cout<<i<<" "; cout<<endl;
      |  ^~~
railway.cpp:106:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  106 |  for(int i : ans) cout<<i<<" "; cout<<endl;
      |                                 ^~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 500 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 181 ms 58348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 179 ms 57864 KB Output is correct
4 Correct 162 ms 57540 KB Output is correct
5 Correct 180 ms 56680 KB Output is correct
6 Correct 161 ms 56672 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 51692 KB Output is correct
2 Correct 188 ms 49832 KB Output is correct
3 Correct 206 ms 55496 KB Output is correct
4 Correct 198 ms 55560 KB Output is correct
5 Correct 207 ms 55748 KB Output is correct
6 Correct 159 ms 52088 KB Output is correct
7 Correct 161 ms 51912 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 51692 KB Output is correct
2 Correct 188 ms 49832 KB Output is correct
3 Correct 206 ms 55496 KB Output is correct
4 Correct 198 ms 55560 KB Output is correct
5 Correct 207 ms 55748 KB Output is correct
6 Correct 159 ms 52088 KB Output is correct
7 Correct 161 ms 51912 KB Output is correct
8 Correct 180 ms 52232 KB Output is correct
9 Correct 175 ms 51664 KB Output is correct
10 Correct 156 ms 56520 KB Output is correct
11 Correct 153 ms 56468 KB Output is correct
12 Incorrect 125 ms 49356 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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