oj.uz

Submission #72534

# Submission time Handle Problem Language Result Execution time Memory
72534 2018-08-26T08:52:12 Z IDxTree(#2155, TAMREF, imeimi2000, Diuven) Chocolate Cookie Machine (FXCUP3_chocolate) C++17
83 / 100
 1054 ms 27240 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef long long ll;
const int inf=2e9, MX=300010;

vector<int> G[MX];
int n, m, k, e;
bool boom[MX];
vector<pib> Q;

pib in(){
	int v; char c; string S;
	cin>>c>>c>>v>>c>>S;
	return {v, S=="BOOM"};
}

bool explode(int a, int b){
	if(boom[a] || boom[b]) return true;
	auto it=lower_bound(G[a].begin(), G[a].end(), b);
	if(it==G[a].end() || *it!=b) return false;
	else return true;
}

bool valid(int s){
	for(pib p:Q){
		int v; bool b; tie(v,b)=p;
		if(explode(v,s)!=b) return false;
	}
	return true;
}

void solve1(){
	for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());
	vector<int> ans;
	for(int i=1; i<=n; i++) if(valid(i)) ans.push_back(i);
	cout<<ans.size()<<'\n';
	for(int x:ans) cout<<x<<' ';
	cout<<'\n';
}

void solve2(){
	int cnt[MX]={}, f=0;
	for(pib p:Q){
		int v; bool b; tie(v,b)=p;
		if(boom[v]){ f++; continue; }

		if(b) for(int x:G[v]) cnt[x]++;
		else assert(false);
	}
	vector<int> ans;
	for(int i=1; i<=n; i++){
		if(boom[i] || cnt[i]==e-f) ans.push_back(i);
	}
	cout<<ans.size()<<'\n';
	for(int x:ans) cout<<x<<' ';
	cout<<'\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1,x ; i<=m; i++) cin>>x, boom[x]=true;
	for(int i=1; i<=k; i++){
		int u,v; cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	cin>>e;
	for(int i=1; i<=e; i++){
		int v; bool b; tie(v,b)=in();
		Q.push_back({v,b});
	}
	
	if(n<=1000) solve1();
	else solve2();
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7292 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 17 ms 7728 KB Output is correct
4 Correct 120 ms 11828 KB Output is correct
5 Correct 11 ms 11828 KB Output is correct
6 Correct 10 ms 11828 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 20660 KB Output is correct
2 Correct 111 ms 20660 KB Output is correct
3 Correct 360 ms 20660 KB Output is correct
4 Correct 897 ms 25556 KB Output is correct
5 Correct 369 ms 25556 KB Output is correct
6 Correct 52 ms 25556 KB Output is correct
7 Correct 1054 ms 27240 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7292 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 17 ms 7728 KB Output is correct
4 Correct 120 ms 11828 KB Output is correct
5 Correct 11 ms 11828 KB Output is correct
6 Correct 10 ms 11828 KB Output is correct
7 Correct 529 ms 20660 KB Output is correct
8 Correct 111 ms 20660 KB Output is correct
9 Correct 360 ms 20660 KB Output is correct
10 Correct 897 ms 25556 KB Output is correct
11 Correct 369 ms 25556 KB Output is correct
12 Correct 52 ms 25556 KB Output is correct
13 Correct 1054 ms 27240 KB Output is correct
14 Runtime error 24 ms 27240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -