oj.uz

Submission #213461

# Submission time Handle Problem Language Result Execution time Memory
213461 2020-03-25T21:56:46 Z rqi Game (IOI14_game) C++14
100 / 100
 489 ms 24700 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 



/**
 * Description: Disjoint Set Union with path compression. 
 	* Add edges and test connectivity. Use for Kruskal's 
 	* minimum spanning tree.
 * Time: O(\alpha(N))
 * Source: CSAcademy, KACTL
 * Verification: USACO superbull
 */

struct DSU {
	vi e; void init(int n) { e = vi(n,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union-by-rank
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

/**template<class T> T kruskal(int n, vector<pair<T,pi>> ed) {
	sort(all(ed));
	T ans = 0; DSU D; D.init(n+1); // edges that unite are in MST
	trav(a,ed) if (D.unite(a.s.f,a.s.s)) ans += a.f; 
	return ans;
}*/


DSU dsu;
bool adj[1505][1505]; //edge was queried between them
int N;
int ednum[1505][1505];
void initialize(int n) {
	N = n;
	dsu.init(n+5);
}



int hasEdge(int u, int v) {
	u = dsu.get(u);
	v = dsu.get(v);
	if(u > v) swap(u, v);
	if(u == v){
		return 1;
	}

	ednum[u][v]++;
	//how many edges between the two components?
	if(ednum[u][v] < dsu.size(u)*dsu.size(v)){
		return 0;
	}
	//merge
	vi anses(N, 0);
	for(int i = 0; i < N; i++){
		int a = i;
		int b = u;
		if(a > b) swap(a, b);
		anses[i]+=ednum[a][b];
	}

	for(int i = 0; i < N; i++){
		int a = i;
		int b = v;
		if(a > b) swap(a, b);
		anses[i]+=ednum[a][b];
	}
	dsu.unite(u, v);
	u = dsu.get(u);
	for(int i = 0; i < N; i++){
		int a = i;
		int b = u;
		if(a > b) swap(a, b);
		ednum[a][b] = anses[i];
	}
	return 1;
}

Compilation message

game.cpp: In function 'void setIn(std::__cxx11::string)':
game.cpp:124:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void setOut(std::__cxx11::string)':
game.cpp:125:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 512 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 512 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 512 KB Output is correct
32 Correct 5 ms 512 KB Output is correct
33 Correct 5 ms 512 KB Output is correct
34 Correct 6 ms 640 KB Output is correct
35 Correct 6 ms 640 KB Output is correct
36 Correct 6 ms 640 KB Output is correct
37 Correct 6 ms 640 KB Output is correct
38 Correct 6 ms 640 KB Output is correct
39 Correct 6 ms 640 KB Output is correct
40 Correct 6 ms 640 KB Output is correct
41 Correct 6 ms 640 KB Output is correct
42 Correct 6 ms 640 KB Output is correct
43 Correct 6 ms 384 KB Output is correct
44 Correct 6 ms 768 KB Output is correct
45 Correct 6 ms 640 KB Output is correct
46 Correct 6 ms 640 KB Output is correct
47 Correct 6 ms 768 KB Output is correct
48 Correct 6 ms 640 KB Output is correct
49 Correct 6 ms 640 KB Output is correct
50 Correct 6 ms 768 KB Output is correct
51 Correct 6 ms 640 KB Output is correct
52 Correct 6 ms 640 KB Output is correct
53 Correct 6 ms 640 KB Output is correct
54 Correct 6 ms 640 KB Output is correct

Subtask #3
58.0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 512 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 512 KB Output is correct
29 Correct 5 ms 512 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 512 KB Output is correct
32 Correct 5 ms 512 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 6 ms 640 KB Output is correct
35 Correct 6 ms 640 KB Output is correct
36 Correct 6 ms 768 KB Output is correct
37 Correct 7 ms 640 KB Output is correct
38 Correct 6 ms 768 KB Output is correct
39 Correct 6 ms 640 KB Output is correct
40 Correct 6 ms 640 KB Output is correct
41 Correct 6 ms 640 KB Output is correct
42 Correct 6 ms 640 KB Output is correct
43 Correct 6 ms 384 KB Output is correct
44 Correct 7 ms 768 KB Output is correct
45 Correct 6 ms 768 KB Output is correct
46 Correct 6 ms 640 KB Output is correct
47 Correct 6 ms 640 KB Output is correct
48 Correct 6 ms 640 KB Output is correct
49 Correct 6 ms 640 KB Output is correct
50 Correct 6 ms 640 KB Output is correct
51 Correct 7 ms 768 KB Output is correct
52 Correct 6 ms 640 KB Output is correct
53 Correct 6 ms 768 KB Output is correct
54 Correct 6 ms 640 KB Output is correct
55 Correct 56 ms 4472 KB Output is correct
56 Correct 55 ms 4600 KB Output is correct
57 Correct 56 ms 4472 KB Output is correct
58 Correct 56 ms 4600 KB Output is correct
59 Correct 56 ms 4472 KB Output is correct
60 Correct 57 ms 4472 KB Output is correct
61 Correct 55 ms 4472 KB Output is correct
62 Correct 56 ms 4472 KB Output is correct
63 Correct 56 ms 4600 KB Output is correct
64 Correct 52 ms 2168 KB Output is correct
65 Correct 54 ms 4216 KB Output is correct
66 Correct 55 ms 4472 KB Output is correct
67 Correct 58 ms 4728 KB Output is correct
68 Correct 56 ms 4600 KB Output is correct
69 Correct 55 ms 4344 KB Output is correct
70 Correct 56 ms 4600 KB Output is correct
71 Correct 56 ms 4728 KB Output is correct
72 Correct 58 ms 4600 KB Output is correct
73 Correct 56 ms 4472 KB Output is correct
74 Correct 56 ms 4600 KB Output is correct
75 Correct 56 ms 4716 KB Output is correct
76 Correct 124 ms 8312 KB Output is correct
77 Correct 123 ms 8444 KB Output is correct
78 Correct 130 ms 8440 KB Output is correct
79 Correct 121 ms 8440 KB Output is correct
80 Correct 134 ms 8312 KB Output is correct
81 Correct 123 ms 8312 KB Output is correct
82 Correct 123 ms 8316 KB Output is correct
83 Correct 121 ms 8312 KB Output is correct
84 Correct 122 ms 8568 KB Output is correct
85 Correct 215 ms 12920 KB Output is correct
86 Correct 213 ms 12792 KB Output is correct
87 Correct 211 ms 12920 KB Output is correct
88 Correct 207 ms 12792 KB Output is correct
89 Correct 214 ms 12792 KB Output is correct
90 Correct 213 ms 12664 KB Output is correct
91 Correct 216 ms 12792 KB Output is correct
92 Correct 221 ms 12920 KB Output is correct
93 Correct 227 ms 12920 KB Output is correct
94 Correct 465 ms 24312 KB Output is correct
95 Correct 487 ms 24696 KB Output is correct
96 Correct 482 ms 24700 KB Output is correct
97 Correct 476 ms 24568 KB Output is correct
98 Correct 487 ms 24568 KB Output is correct
99 Correct 489 ms 24544 KB Output is correct
100 Correct 474 ms 24112 KB Output is correct