답안 #75793 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75793	2018-09-11T06:54:34 Z	tmwilliamlin168	늑대인간 (IOI18_werewolf)	C++14	100 / 100	772 ms	65844 KB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=2e5;
int n, q, p[mxN], st[2][mxN], en[2][mxN], dt, anc[2][mxN], r[mxN], ta[mxN], ft[mxN+1];
vector<int> adj1[mxN], adj2[mxN];
vector<array<int, 2>> b[mxN+1];
bool d[mxN];

int find(int x) {
	return x==r[x]?x:(r[x]=find(r[x]));
}

void dfs(int u, int st[mxN], int en[mxN]) {
	st[u]=dt++;
	for(int v : adj2[u])
		dfs(v, st, en);
	en[u]=dt;
}

void a(int st[mxN], int en[mxN], int anc[mxN]) {
	for(int i=0; i<n; ++i)
		r[i]=i;
	for(int i=0; i<n; ++i) {
		for(int j : adj1[p[i]]) {
			if(!d[j]||(j=find(j))==p[i])
				continue;
			r[j]=p[i];
			adj2[p[i]].push_back(j);
		}
		for(array<int, 2> c : b[p[i]])
			anc[c[1]]=find(c[0]);
		b[p[i]].clear();
		d[p[i]]=1;
	}
	dfs(p[n-1], st, en);
}

int qry(int i) {
	int r=0;
	for(; i; i-=i&-i)
		r+=ft[i];
	return r;
}

vector<int> check_validity(int n2, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
	n=n2;
	for(int i=0; i<x.size(); ++i) {
		adj1[x[i]].push_back(y[i]);
		adj1[y[i]].push_back(x[i]);
	}
	q=s.size();
	for(int i=0; i<n; ++i)
		p[i]=n-1-i;
	for(int i=0; i<q; ++i)
		b[l[i]].push_back({s[i], i});
	a(st[0], en[0], anc[0]);
	for(int i=0; i<n; ++i) {
		adj2[i].clear();
		p[i]=i;
	}
	memset(d, 0, n);
	dt=0;
	for(int i=0; i<q; ++i)
		b[r[i]].push_back({e[i], i});
	a(st[1], en[1], anc[1]);
	for(int i=0; i<n; ++i)
		ta[st[0][i]]=st[1][i];
	for(int i=0; i<q; ++i) {
		b[st[0][anc[0][i]]].push_back({i, -1});
		b[en[0][anc[0][i]]].push_back({i, 1});
	}
	vector<int> ans=vector<int>(q);
	for(int i=0; i<n; ++i) {
		for(int j=ta[i]+1; j<=n; j+=j&-j)
			++ft[j];
		for(array<int, 2> c : b[i+1])
			ans[c[0]]+=c[1]*(qry(en[1][anc[1][c[0]]])-qry(st[1][anc[1][c[0]]]));
	}
	for(int i=0; i<q; ++i)
		ans[i]=ans[i]>0;
	return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<x.size(); ++i) {
               ~^~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	14456 KB	Output is correct
2	Correct	15 ms	14584 KB	Output is correct
3	Correct	14 ms	14664 KB	Output is correct
4	Correct	18 ms	14664 KB	Output is correct
5	Correct	14 ms	14664 KB	Output is correct
6	Correct	14 ms	14740 KB	Output is correct
7	Correct	14 ms	14740 KB	Output is correct
8	Correct	15 ms	14740 KB	Output is correct
9	Correct	15 ms	14748 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	14456 KB	Output is correct
2	Correct	15 ms	14584 KB	Output is correct
3	Correct	14 ms	14664 KB	Output is correct
4	Correct	18 ms	14664 KB	Output is correct
5	Correct	14 ms	14664 KB	Output is correct
6	Correct	14 ms	14740 KB	Output is correct
7	Correct	14 ms	14740 KB	Output is correct
8	Correct	15 ms	14740 KB	Output is correct
9	Correct	15 ms	14748 KB	Output is correct
10	Correct	21 ms	15388 KB	Output is correct
11	Correct	20 ms	15444 KB	Output is correct
12	Correct	28 ms	15444 KB	Output is correct
13	Correct	20 ms	15612 KB	Output is correct
14	Correct	22 ms	15612 KB	Output is correct
15	Correct	22 ms	15612 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	671 ms	55460 KB	Output is correct
2	Correct	601 ms	59820 KB	Output is correct
3	Correct	605 ms	59820 KB	Output is correct
4	Correct	592 ms	59820 KB	Output is correct
5	Correct	627 ms	59820 KB	Output is correct
6	Correct	668 ms	59820 KB	Output is correct
7	Correct	570 ms	59820 KB	Output is correct
8	Correct	601 ms	59820 KB	Output is correct
9	Correct	516 ms	59820 KB	Output is correct
10	Correct	519 ms	59820 KB	Output is correct
11	Correct	509 ms	59820 KB	Output is correct
12	Correct	566 ms	59820 KB	Output is correct
13	Correct	576 ms	59820 KB	Output is correct
14	Correct	623 ms	59820 KB	Output is correct
15	Correct	602 ms	59820 KB	Output is correct
16	Correct	624 ms	59820 KB	Output is correct
17	Correct	591 ms	59820 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	14456 KB	Output is correct
2	Correct	15 ms	14584 KB	Output is correct
3	Correct	14 ms	14664 KB	Output is correct
4	Correct	18 ms	14664 KB	Output is correct
5	Correct	14 ms	14664 KB	Output is correct
6	Correct	14 ms	14740 KB	Output is correct
7	Correct	14 ms	14740 KB	Output is correct
8	Correct	15 ms	14740 KB	Output is correct
9	Correct	15 ms	14748 KB	Output is correct
10	Correct	21 ms	15388 KB	Output is correct
11	Correct	20 ms	15444 KB	Output is correct
12	Correct	28 ms	15444 KB	Output is correct
13	Correct	20 ms	15612 KB	Output is correct
14	Correct	22 ms	15612 KB	Output is correct
15	Correct	22 ms	15612 KB	Output is correct
16	Correct	671 ms	55460 KB	Output is correct
17	Correct	601 ms	59820 KB	Output is correct
18	Correct	605 ms	59820 KB	Output is correct
19	Correct	592 ms	59820 KB	Output is correct
20	Correct	627 ms	59820 KB	Output is correct
21	Correct	668 ms	59820 KB	Output is correct
22	Correct	570 ms	59820 KB	Output is correct
23	Correct	601 ms	59820 KB	Output is correct
24	Correct	516 ms	59820 KB	Output is correct
25	Correct	519 ms	59820 KB	Output is correct
26	Correct	509 ms	59820 KB	Output is correct
27	Correct	566 ms	59820 KB	Output is correct
28	Correct	576 ms	59820 KB	Output is correct
29	Correct	623 ms	59820 KB	Output is correct
30	Correct	602 ms	59820 KB	Output is correct
31	Correct	624 ms	59820 KB	Output is correct
32	Correct	591 ms	59820 KB	Output is correct
33	Correct	769 ms	59820 KB	Output is correct
34	Correct	367 ms	59820 KB	Output is correct
35	Correct	725 ms	59820 KB	Output is correct
36	Correct	705 ms	59820 KB	Output is correct
37	Correct	736 ms	59820 KB	Output is correct
38	Correct	647 ms	59820 KB	Output is correct
39	Correct	671 ms	65072 KB	Output is correct
40	Correct	772 ms	65072 KB	Output is correct
41	Correct	610 ms	65072 KB	Output is correct
42	Correct	562 ms	65072 KB	Output is correct
43	Correct	718 ms	65072 KB	Output is correct
44	Correct	662 ms	65072 KB	Output is correct
45	Correct	583 ms	65092 KB	Output is correct
46	Correct	652 ms	65844 KB	Output is correct
47	Correct	599 ms	65844 KB	Output is correct
48	Correct	617 ms	65844 KB	Output is correct
49	Correct	585 ms	65844 KB	Output is correct
50	Correct	594 ms	65844 KB	Output is correct
51	Correct	653 ms	65844 KB	Output is correct
52	Correct	636 ms	65844 KB	Output is correct

답안 #75793

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 34.0 / 34.0

Subtask #4 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
34.0 / 34.0

Subtask #4
51.0 / 51.0