oj.uz

답안 #115249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115249 2019-06-06T11:12:15 Z claudy 늑대인간 (IOI18_werewolf) C++14
100 / 100
 1010 ms 142016 KB 
# include "werewolf.h"
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int n,q;
vector<int>eul[2];
vector<int>vec[1 << 18],vek[2][1 << 18],QRY[2][1 << 18];
vector<pair<int,int>>qry[2][1 << 18],add[1 << 18],sub[1 << 18];
int fen[1 << 18],p[2][1 << 18],SZ[2][1 << 18];
pair<int,int>seg[2][1 << 19];

int Qry(int idx)
{
	if(idx < 0) return 0;
	idx++;
	int ans = 0;
	for(int i = idx;i;i -= (i & (-i))) ans += fen[i];
	return ans;
}

void upd(int idx)
{
	idx++;
	for(int i = idx;i <= n;i += (i & (-i))) fen[i] += 1;
}

int find(int x,int op)
{
	if(p[op][x] == x) return x;
	return p[op][x] = find(p[op][x],op);
}

void dfs(int nod,int par,int op)
{
	SZ[op][nod] = 1;
	eul[op].pb(nod);
	int idx = sz(eul[op]) - 1;
	for(auto it : vek[op][nod])
	{
		if(it != par)
		{
			dfs(it,nod,op);
			SZ[op][nod] += SZ[op][it];
		}
	}
	for(auto it : QRY[op][nod])
	{
		seg[op][it] = mp(idx,idx + SZ[op][nod] - 1);
	}
}

vector<int>check_validity(int N, vector<int>X, vector<int>Y, vector<int>S, vector<int>E, vector<int>L, vector<int>R)
{
	n = N;
	q = sz(S);
	for(int i = 0;i < sz(X);i++)
	{
		int a = X[i];
		int b = Y[i];
		a++;b++;
		vec[a].pb(b);
		vec[b].pb(a);
	}
	for(int i = 0;i < q;i++)
	{
		qry[0][L[i] + 1].pb(mp(i,S[i] + 1));
		qry[1][R[i] + 1].pb(mp(i,E[i] + 1));
	}
	for(int i = n;i >= 1;i--)
	{
		p[0][i] = i;
		for(auto it : vec[i])
		{
			if(it < i) continue;
			int x = find(i,0);
			int y = find(it,0);
			if(x != y)
			{
				p[0][y] = x;
				vek[0][x].pb(y);
			}
		}
		for(auto it : qry[0][i])
		{
			QRY[0][find(it.second,0)].pb(it.first);
		}
	}
	for(int i = 1;i <= n;i++)
	{
		p[1][i] = i;
		for(auto it : vec[i])
		{
			if(it > i) continue;
			int x = find(i,1);
			int y = find(it,1);
			if(x != y)
			{
				p[1][y] = x;
				vek[1][x].pb(y);
			}
		}
		for(auto it : qry[1][i])
		{
			QRY[1][find(it.second,1)].pb(it.first);
		}
	}
	/*for(int i = 1;i <= n;i++)
	{
		for(auto it : vek[0][i]) cout << it << ' ';
		cout << '\n';
	}
	cout << "-------------------\n";
	for(int i = 1;i <= n;i++)
	{
		for(auto it : vek[1][i]) cout << it << ' ';
		cout << '\n';
	}*/
	dfs(1,0,0);
	dfs(n,0,1);
	vector<int>ans(q,0);
	for(int i = 0;i < q;i++)
	{
		int l0 = seg[0][i].first;int r0 = seg[0][i].second;
		int l1 = seg[1][i].first;int r1 = seg[1][i].second;
		add[r1].pb(mp(i,r0));
		sub[r1].pb(mp(i,l0 - 1));
		if(!l1) continue;
		sub[l1 - 1].pb(mp(i,r0));
		add[l1 - 1].pb(mp(i,l0 - 1));
	}
	int idx[n];
	for(int i = 0;i < n;i++)
	{
		idx[eul[0][i]] = i;
	}
	for(int i = 0;i < n;i++)
	{
		upd(idx[eul[1][i]]);
		for(auto it : add[i])
		{
			ans[it.first] += Qry(it.second);
		}
		for(auto it : sub[i])
		{
			ans[it.first] -= Qry(it.second);
		}
	}
	for(auto &it : ans)
	{
		it = (bool)(it);
	}
	return ans;
}

/*
int32_t main(){_
	//freopen("input","r",stdin);

	return 0;
}*/

Compilation message

werewolf.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 55800 KB Output is correct
2 Correct 49 ms 55800 KB Output is correct
3 Correct 49 ms 55800 KB Output is correct
4 Correct 49 ms 55752 KB Output is correct
5 Correct 49 ms 55800 KB Output is correct
6 Correct 50 ms 55800 KB Output is correct
7 Correct 49 ms 55800 KB Output is correct
8 Correct 51 ms 55800 KB Output is correct
9 Correct 49 ms 55844 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 55800 KB Output is correct
2 Correct 49 ms 55800 KB Output is correct
3 Correct 49 ms 55800 KB Output is correct
4 Correct 49 ms 55752 KB Output is correct
5 Correct 49 ms 55800 KB Output is correct
6 Correct 50 ms 55800 KB Output is correct
7 Correct 49 ms 55800 KB Output is correct
8 Correct 51 ms 55800 KB Output is correct
9 Correct 49 ms 55844 KB Output is correct
10 Correct 55 ms 56824 KB Output is correct
11 Correct 56 ms 56824 KB Output is correct
12 Correct 55 ms 56692 KB Output is correct
13 Correct 57 ms 57080 KB Output is correct
14 Correct 54 ms 57080 KB Output is correct
15 Correct 57 ms 56876 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1010 ms 121340 KB Output is correct
2 Correct 737 ms 122412 KB Output is correct
3 Correct 729 ms 116784 KB Output is correct
4 Correct 724 ms 115620 KB Output is correct
5 Correct 764 ms 115824 KB Output is correct
6 Correct 814 ms 118520 KB Output is correct
7 Correct 706 ms 113640 KB Output is correct
8 Correct 759 ms 123096 KB Output is correct
9 Correct 642 ms 115524 KB Output is correct
10 Correct 535 ms 111372 KB Output is correct
11 Correct 614 ms 113280 KB Output is correct
12 Correct 668 ms 113388 KB Output is correct
13 Correct 800 ms 131856 KB Output is correct
14 Correct 792 ms 131696 KB Output is correct
15 Correct 779 ms 131828 KB Output is correct
16 Correct 775 ms 131624 KB Output is correct
17 Correct 675 ms 113984 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 55800 KB Output is correct
2 Correct 49 ms 55800 KB Output is correct
3 Correct 49 ms 55800 KB Output is correct
4 Correct 49 ms 55752 KB Output is correct
5 Correct 49 ms 55800 KB Output is correct
6 Correct 50 ms 55800 KB Output is correct
7 Correct 49 ms 55800 KB Output is correct
8 Correct 51 ms 55800 KB Output is correct
9 Correct 49 ms 55844 KB Output is correct
10 Correct 55 ms 56824 KB Output is correct
11 Correct 56 ms 56824 KB Output is correct
12 Correct 55 ms 56692 KB Output is correct
13 Correct 57 ms 57080 KB Output is correct
14 Correct 54 ms 57080 KB Output is correct
15 Correct 57 ms 56876 KB Output is correct
16 Correct 1010 ms 121340 KB Output is correct
17 Correct 737 ms 122412 KB Output is correct
18 Correct 729 ms 116784 KB Output is correct
19 Correct 724 ms 115620 KB Output is correct
20 Correct 764 ms 115824 KB Output is correct
21 Correct 814 ms 118520 KB Output is correct
22 Correct 706 ms 113640 KB Output is correct
23 Correct 759 ms 123096 KB Output is correct
24 Correct 642 ms 115524 KB Output is correct
25 Correct 535 ms 111372 KB Output is correct
26 Correct 614 ms 113280 KB Output is correct
27 Correct 668 ms 113388 KB Output is correct
28 Correct 800 ms 131856 KB Output is correct
29 Correct 792 ms 131696 KB Output is correct
30 Correct 779 ms 131828 KB Output is correct
31 Correct 775 ms 131624 KB Output is correct
32 Correct 675 ms 113984 KB Output is correct
33 Correct 909 ms 121568 KB Output is correct
34 Correct 356 ms 104560 KB Output is correct
35 Correct 931 ms 129364 KB Output is correct
36 Correct 991 ms 124232 KB Output is correct
37 Correct 908 ms 127980 KB Output is correct
38 Correct 953 ms 125112 KB Output is correct
39 Correct 831 ms 142016 KB Output is correct
40 Correct 797 ms 128932 KB Output is correct
41 Correct 760 ms 121428 KB Output is correct
42 Correct 641 ms 115828 KB Output is correct
43 Correct 944 ms 134260 KB Output is correct
44 Correct 795 ms 123908 KB Output is correct
45 Correct 780 ms 141212 KB Output is correct
46 Correct 764 ms 141024 KB Output is correct
47 Correct 775 ms 135164 KB Output is correct
48 Correct 795 ms 134936 KB Output is correct
49 Correct 825 ms 135020 KB Output is correct
50 Correct 767 ms 135020 KB Output is correct
51 Correct 715 ms 124792 KB Output is correct
52 Correct 739 ms 125040 KB Output is correct