oj.uz

답안 #314969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314969 2020-10-21T18:15:56 Z jc713 다리 (APIO19_bridges) C++17
100 / 100
 2979 ms 11216 KB 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!
 
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>; 
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>; 
using vpd = vector<pd>;
 
#define tcT template<class T
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
 
// pairs
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#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 
 
// loops
#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; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
 
// helper funcs
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
#define tcTU tcT, class U
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
	auto it = t.find(u); assert(it != end(t));
	t.erase(u); } // element that doesn't exist from (multi)set
 
// INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(vector<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);
 
tcT> 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); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(vector<T>& x) { trav(a,x) re(a); }
tcT, size_t SZ> void re(AR<T,SZ>& x) { trav(a,x) re(a); }
 
// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
tcT> str ts(complex<T> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+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; }
tcTU> str ts(pair<T,U> p);
tcT> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
 
	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}
 
// OUTPUT
tcT> void pr(T x) { cout << ts(x); }
tcTUU> void pr(const T& t, const U&... u) { 
	pr(t); pr(u...); }
void ps() { pr("\n"); } // print w/ spaces
tcTUU> void ps(const T& t, const U&... u) { 
	pr(t); if (sizeof...(u)) pr(" "); ps(u...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
	cerr << ts(t); if (sizeof...(u)) cerr << ", ";
	DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif
 
// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str 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
}
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
const int BLOCK = 1050;
 
struct DSUrb {
	vi e; void init(int n) { e = vi(n,-1); }
	int get(int x) { return e[x] < 0 ? x : get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	vector<pair<pi, pi>> mod;
	bool unite(int x, int y) { // union-by-rank
		x = get(x), y = get(y); 
		if (x == y) { mod.pb({{-1,-1},{-1,-1}}); return 0; }
		if (e[x] > e[y]) swap(x,y);
		mod.pb({{x,y},{e[x],e[y]}});
		e[x] += e[y]; e[y] = x; return 1;
	}
	void rollback() {
		auto a = mod.bk; mod.pop_back();
		if (a.f.f != -1) e[a.f.f] = a.s.f, e[a.f.s] = a.s.s;
	}
};

int n1[100010], n2[100010], lim[100010];
bool changed[100010];
 
int main(){
	setIO();
	int n, m;
	cin >> n >> m;
	F0R(a, m){
		cin >> n1[a] >> n2[a] >> lim[a];
		n1[a]--, n2[a]--;
	}
	int q;
	cin >> q;
	while(q > 0){
		DSUrb D;
		D.init(n);
		int size = min(q, BLOCK);
		int ans[size];
		fill(ans, ans + size, -1);
		int type[size], loc[size], w[size];
		memset(changed, 0, sizeof changed);
		vi connect[size];
		vi Q;
		F0R(a, size){
			cin >> type[a] >> loc[a] >> w[a];
			loc[a]--;
			if(type[a] == 1)
				changed[loc[a]] = true;
			else
				Q.pb(a);
		}
		vector<pi> sorted;
		vi ch;
		F0R(a, m)
			if(!changed[a])
				sorted.pb({lim[a], a});
			else
				ch.pb(a);
		F0R(a, size){
			if(type[a] == 1)
				lim[loc[a]] = w[a];
			else{
				trav(b, ch)
					if(lim[b] >= w[a])
						connect[a].pb(b);
			}
		}
		trav(a, Q)
			sorted.pb({w[a], -a-1});
		sort(all(sorted));
		R0F(a, sz(sorted)){
			if(sorted[a].s >= 0)
				D.unite(n1[sorted[a].s], n2[sorted[a].s]);
			else{
				trav(b, connect[-sorted[a].s-1])
					D.unite(n1[b], n2[b]);
				ans[-sorted[a].s-1] = D.size(loc[-sorted[a].s-1]);
				trav(b, connect[-sorted[a].s-1])
					D.rollback();
			}
		}
		F0R(a, size)
			if(ans[a] != -1)
				cout << ans[a] << endl;
		q -= BLOCK;
	}
	// you should actually read the stuff at the bottom
}
 
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:286:10: warning: unused variable 'b' [-Wunused-variable]
  286 |     trav(b, connect[-sorted[a].s-1])
      |          ^
bridges.cpp:52:30: note: in definition of macro 'trav'
   52 | #define trav(a,x) for (auto& a: x)
      |                              ^
bridges.cpp: In function 'void setIn(str)':
bridges.cpp:182:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  182 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void setOut(str)':
bridges.cpp:183:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  183 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 51 ms 1232 KB Output is correct
4 Correct 26 ms 512 KB Output is correct
5 Correct 24 ms 756 KB Output is correct
6 Correct 22 ms 732 KB Output is correct
7 Correct 23 ms 736 KB Output is correct
8 Correct 24 ms 692 KB Output is correct
9 Correct 26 ms 860 KB Output is correct
10 Correct 26 ms 740 KB Output is correct
11 Correct 24 ms 716 KB Output is correct
12 Correct 26 ms 804 KB Output is correct
13 Correct 31 ms 836 KB Output is correct
14 Correct 30 ms 780 KB Output is correct
15 Correct 27 ms 756 KB Output is correct
16 Correct 24 ms 768 KB Output is correct
17 Correct 26 ms 848 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1554 ms 4452 KB Output is correct
2 Correct 1511 ms 4692 KB Output is correct
3 Correct 1520 ms 4620 KB Output is correct
4 Correct 1500 ms 4724 KB Output is correct
5 Correct 1516 ms 4812 KB Output is correct
6 Correct 2015 ms 6288 KB Output is correct
7 Correct 2020 ms 6268 KB Output is correct
8 Correct 2017 ms 5992 KB Output is correct
9 Correct 247 ms 760 KB Output is correct
10 Correct 1502 ms 5592 KB Output is correct
11 Correct 1479 ms 5112 KB Output is correct
12 Correct 1451 ms 4760 KB Output is correct
13 Correct 1151 ms 4112 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1189 ms 3648 KB Output is correct
2 Correct 850 ms 2692 KB Output is correct
3 Correct 1352 ms 4240 KB Output is correct
4 Correct 1200 ms 3220 KB Output is correct
5 Correct 246 ms 700 KB Output is correct
6 Correct 1296 ms 3572 KB Output is correct
7 Correct 1118 ms 3340 KB Output is correct
8 Correct 983 ms 3108 KB Output is correct
9 Correct 960 ms 3340 KB Output is correct
10 Correct 902 ms 3112 KB Output is correct
11 Correct 749 ms 2960 KB Output is correct
12 Correct 680 ms 2644 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1988 ms 7124 KB Output is correct
2 Correct 246 ms 760 KB Output is correct
3 Correct 210 ms 6208 KB Output is correct
4 Correct 225 ms 6268 KB Output is correct
5 Correct 1949 ms 7064 KB Output is correct
6 Correct 2009 ms 7168 KB Output is correct
7 Correct 1962 ms 6924 KB Output is correct
8 Correct 1050 ms 4024 KB Output is correct
9 Correct 1040 ms 3872 KB Output is correct
10 Correct 1047 ms 4112 KB Output is correct
11 Correct 1575 ms 5880 KB Output is correct
12 Correct 1562 ms 5828 KB Output is correct
13 Correct 1609 ms 6164 KB Output is correct
14 Correct 1820 ms 7192 KB Output is correct
15 Correct 1885 ms 7192 KB Output is correct
16 Correct 2003 ms 6964 KB Output is correct
17 Correct 2029 ms 6868 KB Output is correct
18 Correct 1993 ms 6812 KB Output is correct
19 Correct 1992 ms 6776 KB Output is correct
20 Correct 1726 ms 6300 KB Output is correct
21 Correct 1762 ms 6636 KB Output is correct
22 Correct 1959 ms 6864 KB Output is correct
23 Correct 1806 ms 6252 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1554 ms 4452 KB Output is correct
2 Correct 1511 ms 4692 KB Output is correct
3 Correct 1520 ms 4620 KB Output is correct
4 Correct 1500 ms 4724 KB Output is correct
5 Correct 1516 ms 4812 KB Output is correct
6 Correct 2015 ms 6288 KB Output is correct
7 Correct 2020 ms 6268 KB Output is correct
8 Correct 2017 ms 5992 KB Output is correct
9 Correct 247 ms 760 KB Output is correct
10 Correct 1502 ms 5592 KB Output is correct
11 Correct 1479 ms 5112 KB Output is correct
12 Correct 1451 ms 4760 KB Output is correct
13 Correct 1151 ms 4112 KB Output is correct
14 Correct 1189 ms 3648 KB Output is correct
15 Correct 850 ms 2692 KB Output is correct
16 Correct 1352 ms 4240 KB Output is correct
17 Correct 1200 ms 3220 KB Output is correct
18 Correct 246 ms 700 KB Output is correct
19 Correct 1296 ms 3572 KB Output is correct
20 Correct 1118 ms 3340 KB Output is correct
21 Correct 983 ms 3108 KB Output is correct
22 Correct 960 ms 3340 KB Output is correct
23 Correct 902 ms 3112 KB Output is correct
24 Correct 749 ms 2960 KB Output is correct
25 Correct 680 ms 2644 KB Output is correct
26 Correct 1530 ms 4628 KB Output is correct
27 Correct 1874 ms 5512 KB Output is correct
28 Correct 1611 ms 4608 KB Output is correct
29 Correct 1238 ms 4048 KB Output is correct
30 Correct 1807 ms 5220 KB Output is correct
31 Correct 1815 ms 5100 KB Output is correct
32 Correct 1806 ms 5124 KB Output is correct
33 Correct 1570 ms 4760 KB Output is correct
34 Correct 1597 ms 4492 KB Output is correct
35 Correct 1603 ms 4472 KB Output is correct
36 Correct 1266 ms 4112 KB Output is correct
37 Correct 1253 ms 4264 KB Output is correct
38 Correct 1246 ms 4216 KB Output is correct
39 Correct 1167 ms 4100 KB Output is correct
40 Correct 1162 ms 4200 KB Output is correct
41 Correct 1156 ms 4128 KB Output is correct
42 Correct 979 ms 4144 KB Output is correct
43 Correct 1000 ms 4228 KB Output is correct
44 Correct 972 ms 4044 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 51 ms 1232 KB Output is correct
4 Correct 26 ms 512 KB Output is correct
5 Correct 24 ms 756 KB Output is correct
6 Correct 22 ms 732 KB Output is correct
7 Correct 23 ms 736 KB Output is correct
8 Correct 24 ms 692 KB Output is correct
9 Correct 26 ms 860 KB Output is correct
10 Correct 26 ms 740 KB Output is correct
11 Correct 24 ms 716 KB Output is correct
12 Correct 26 ms 804 KB Output is correct
13 Correct 31 ms 836 KB Output is correct
14 Correct 30 ms 780 KB Output is correct
15 Correct 27 ms 756 KB Output is correct
16 Correct 24 ms 768 KB Output is correct
17 Correct 26 ms 848 KB Output is correct
18 Correct 1554 ms 4452 KB Output is correct
19 Correct 1511 ms 4692 KB Output is correct
20 Correct 1520 ms 4620 KB Output is correct
21 Correct 1500 ms 4724 KB Output is correct
22 Correct 1516 ms 4812 KB Output is correct
23 Correct 2015 ms 6288 KB Output is correct
24 Correct 2020 ms 6268 KB Output is correct
25 Correct 2017 ms 5992 KB Output is correct
26 Correct 247 ms 760 KB Output is correct
27 Correct 1502 ms 5592 KB Output is correct
28 Correct 1479 ms 5112 KB Output is correct
29 Correct 1451 ms 4760 KB Output is correct
30 Correct 1151 ms 4112 KB Output is correct
31 Correct 1189 ms 3648 KB Output is correct
32 Correct 850 ms 2692 KB Output is correct
33 Correct 1352 ms 4240 KB Output is correct
34 Correct 1200 ms 3220 KB Output is correct
35 Correct 246 ms 700 KB Output is correct
36 Correct 1296 ms 3572 KB Output is correct
37 Correct 1118 ms 3340 KB Output is correct
38 Correct 983 ms 3108 KB Output is correct
39 Correct 960 ms 3340 KB Output is correct
40 Correct 902 ms 3112 KB Output is correct
41 Correct 749 ms 2960 KB Output is correct
42 Correct 680 ms 2644 KB Output is correct
43 Correct 1988 ms 7124 KB Output is correct
44 Correct 246 ms 760 KB Output is correct
45 Correct 210 ms 6208 KB Output is correct
46 Correct 225 ms 6268 KB Output is correct
47 Correct 1949 ms 7064 KB Output is correct
48 Correct 2009 ms 7168 KB Output is correct
49 Correct 1962 ms 6924 KB Output is correct
50 Correct 1050 ms 4024 KB Output is correct
51 Correct 1040 ms 3872 KB Output is correct
52 Correct 1047 ms 4112 KB Output is correct
53 Correct 1575 ms 5880 KB Output is correct
54 Correct 1562 ms 5828 KB Output is correct
55 Correct 1609 ms 6164 KB Output is correct
56 Correct 1820 ms 7192 KB Output is correct
57 Correct 1885 ms 7192 KB Output is correct
58 Correct 2003 ms 6964 KB Output is correct
59 Correct 2029 ms 6868 KB Output is correct
60 Correct 1993 ms 6812 KB Output is correct
61 Correct 1992 ms 6776 KB Output is correct
62 Correct 1726 ms 6300 KB Output is correct
63 Correct 1762 ms 6636 KB Output is correct
64 Correct 1959 ms 6864 KB Output is correct
65 Correct 1806 ms 6252 KB Output is correct
66 Correct 1530 ms 4628 KB Output is correct
67 Correct 1874 ms 5512 KB Output is correct
68 Correct 1611 ms 4608 KB Output is correct
69 Correct 1238 ms 4048 KB Output is correct
70 Correct 1807 ms 5220 KB Output is correct
71 Correct 1815 ms 5100 KB Output is correct
72 Correct 1806 ms 5124 KB Output is correct
73 Correct 1570 ms 4760 KB Output is correct
74 Correct 1597 ms 4492 KB Output is correct
75 Correct 1603 ms 4472 KB Output is correct
76 Correct 1266 ms 4112 KB Output is correct
77 Correct 1253 ms 4264 KB Output is correct
78 Correct 1246 ms 4216 KB Output is correct
79 Correct 1167 ms 4100 KB Output is correct
80 Correct 1162 ms 4200 KB Output is correct
81 Correct 1156 ms 4128 KB Output is correct
82 Correct 979 ms 4144 KB Output is correct
83 Correct 1000 ms 4228 KB Output is correct
84 Correct 972 ms 4044 KB Output is correct
85 Correct 2612 ms 7608 KB Output is correct
86 Correct 260 ms 7056 KB Output is correct
87 Correct 298 ms 8388 KB Output is correct
88 Correct 2618 ms 7828 KB Output is correct
89 Correct 2585 ms 7512 KB Output is correct
90 Correct 2573 ms 7880 KB Output is correct
91 Correct 1652 ms 4704 KB Output is correct
92 Correct 1684 ms 4540 KB Output is correct
93 Correct 2141 ms 5800 KB Output is correct
94 Correct 2243 ms 6720 KB Output is correct
95 Correct 2237 ms 6896 KB Output is correct
96 Correct 2712 ms 7748 KB Output is correct
97 Correct 2173 ms 7912 KB Output is correct
98 Correct 2028 ms 7084 KB Output is correct
99 Correct 2638 ms 7904 KB Output is correct
100 Correct 2614 ms 7964 KB Output is correct
101 Correct 2625 ms 7692 KB Output is correct
102 Correct 2617 ms 7732 KB Output is correct
103 Correct 2942 ms 8468 KB Output is correct
104 Correct 2979 ms 11216 KB Output is correct
105 Correct 2036 ms 9564 KB Output is correct
106 Correct 1638 ms 9080 KB Output is correct
107 Correct 2137 ms 9912 KB Output is correct
108 Correct 2768 ms 10520 KB Output is correct
109 Correct 2656 ms 9980 KB Output is correct