oj.uz

Submission #72316

# Submission time Handle Problem Language Result Execution time Memory
72316 2018-08-26T07:01:56 Z BBBSNG(#2263, youngyojun, sebinkim, dlalswp25) Chocolate Cookie Machine (FXCUP3_chocolate) C++17
100 / 100
 1008 ms 37016 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 300005;
const int MAXM = 300005;
const int MAXK = 1000005;

vector<int> G[MAXN];
vector<int> VA, VB;

bitset<MAXN> isA, isB, isD;

int D[MAXN];

int B[MAXK], C[MAXK];
int A[MAXM];

bitset<MAXN> Ans;
vector<int> AnsV;
int N, M, K, Q, An;

int main() {
	scanf("%d%d%d", &N, &M, &K);
	for(int i = 1; i <= M; i++) scanf("%d", &A[i]);
	for(int i = 1; i <= K; i++) scanf("%d%d", &B[i], &C[i]);
	for(scanf("%d", &Q); Q--;) {
		int x; char str[10];
		scanf(" L + %d = %s", &x, str);
		if('B' == str[0]) VA.eb(x);
		else VB.eb(x);
	}

	for(int i = 1; i <= M; i++) isD[A[i]] = true;
	for(int i = 1; i <= K; i++) fg(G, B[i], C[i]);
	for(int v : VA) {
		if(isD[v]) continue;
		isA[v] = true;
	}
	for(int v : VB) {
		isB[v] = true;
	}

	for(int i = 1; i <= N; i++) if(isA[i]) {
		for(int v : G[i]) D[v]++;
		An++;
	}

	for(int i = 1; i <= M; i++) Ans[A[i]] = true;
	for(int i = 1; i <= N; i++) if(D[i] == An) Ans[i] = true;
	if(!VB.empty()) {
		for(int i = 1; i <= M; i++) Ans[A[i]] = false;
		for(int i = 1; i <= N; i++) if(isB[i])
			for(int v : G[i]) Ans[v] = false;
	}

	for(int i = 1; i <= N; i++) if(Ans[i]) AnsV.eb(i);
	
	printf("%d\n", sz(AnsV));
	for(int v : AnsV) printf("%d ", v);
	puts("");
	return 0;
}

Compilation message

chocolate.cpp: In function 'int main()':
chocolate.cpp:63: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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
chocolate.cpp:64:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= M; i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~
chocolate.cpp:65:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= K; i++) scanf("%d%d", &B[i], &C[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~
chocolate.cpp:66:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d", &Q); Q--;) {
      ~~~~~^~~~~~~~~~
chocolate.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" L + %d = %s", &x, str);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 9 ms 7528 KB Output is correct
3 Correct 14 ms 7712 KB Output is correct
4 Correct 92 ms 14352 KB Output is correct
5 Correct 8 ms 14352 KB Output is correct
6 Correct 10 ms 14352 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 27264 KB Output is correct
2 Correct 121 ms 27264 KB Output is correct
3 Correct 328 ms 27264 KB Output is correct
4 Correct 888 ms 31456 KB Output is correct
5 Correct 439 ms 31456 KB Output is correct
6 Correct 68 ms 31456 KB Output is correct
7 Correct 804 ms 33932 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 9 ms 7528 KB Output is correct
3 Correct 14 ms 7712 KB Output is correct
4 Correct 92 ms 14352 KB Output is correct
5 Correct 8 ms 14352 KB Output is correct
6 Correct 10 ms 14352 KB Output is correct
7 Correct 351 ms 27264 KB Output is correct
8 Correct 121 ms 27264 KB Output is correct
9 Correct 328 ms 27264 KB Output is correct
10 Correct 888 ms 31456 KB Output is correct
11 Correct 439 ms 31456 KB Output is correct
12 Correct 68 ms 31456 KB Output is correct
13 Correct 804 ms 33932 KB Output is correct
14 Correct 15 ms 33932 KB Output is correct
15 Correct 17 ms 33932 KB Output is correct
16 Correct 680 ms 33932 KB Output is correct
17 Correct 205 ms 33932 KB Output is correct
18 Correct 797 ms 36448 KB Output is correct
19 Correct 895 ms 36448 KB Output is correct
20 Correct 792 ms 36448 KB Output is correct
21 Correct 936 ms 36448 KB Output is correct
22 Correct 838 ms 36448 KB Output is correct
23 Correct 1008 ms 37016 KB Output is correct