Submission #39648223

---

Source Code Expand

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 
using ld = long double; 
using str = string; 

using pii = pair<int, int>; 
using pll = pair<ll, ll>; 
#define MP make_pair
#define fs first 
#define sc second

using ull = unsigned long long; 
using mii = map<int, int>; 
using mll = map<ll, ll>; 
#define fd(x, e) (x.find(e) != x.end())

#define tcT template <class T
#define tcTU tcT, class U
#define vt vector //tcT > using vt = vector<T>;
#define ar array // tcT, size_t SZ > using ar = array<T, SZ>;
using vi = vt<int>;
using vb = vt<bool>;
using vl = vt<ll>;
using vd = vt<ld>;
using vs = vt<str>;
using vii = vt<pii>;
using vll = vt<pll>;

#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(x.begin(), x.end()) 
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define ts to_string

#define ub upper_bound
#define lb lower_bound
tcT> int lwb(vt<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT> int upb(vt<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

#define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
#define rp2(i, a, e) for (int (i) = (a); (i) < (int) (e); (i)+=1)
#define rp3(i, a, e, s) for (int (i) = (a); (i) < (int) (e); (i)+=(s))
#define	rpr(i, e) for (int (i) = (e) - 1; i > -1; (i)-=1)
#define rp4(i, a, e) for (int (i) = a; (i) > (int) (e); (i)-=1)
#define rp5(i, a, e, s) for (int (i) = a; (i) > (int) (e); (i)+=(s))
#define E(a, x) for (auto &a: x) 

#define nr(a, n) rp(i, n) {cin >> (a)[i];}
#define nr2(a, n, m) rp(i, n)  rp(j, m) cin >> (a)[i][j]; 
#define quick ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const ld PI = acos((ld)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!!
tcT> using pqg = priority_queue<T, vector<T>, greater<T>>;

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr ll pctll(ll x) { return __builtin_popcountll(x); } 
constexpr int bits(
	int x) { // assert(x >= 0); 
	return x == 0 ? 0 : 31 - __builtin_clz(x);
} // floor(log2(x))
// constexpr int p2(int x) { return 1 << x; }
// constexpr int msk2(int x) { return p2(x) - 1; }

// ------ ------ ------ IO ------ ------ ------ //
template <class A> void re(vt<A>& v);
template <class A, size_t S> void re(array<A, S>& a);

tcT> void re(T& x) { 
	cin >> x;
}
void re(double& d) { 
	string t; 
	re(t); 
	d=stod(t); 
}
void re(long double& d) { 
	string t; 
	re(t); 
	d=stold(t); 
}
tcT> void re(pair<T, T> & p) { 
	T a, b; 
	re(a); 
	re(b); 
	p=make_pair(a, b); 
}
template<class H, class... T> void re(H& h, T&... t) {
	re(h); 
	re(t...); 
}
template<class A> void re(vt<A>& x) { 
	for (auto &a: x) re(a); 
}
template<class A, size_t S> void re(array<A, S>& x) { 
	for (auto &a: x) re(a); 
}
string to_string(char c) { 
	return string(1, c); 
}
string to_string(bool b) { 
	return b?"YES":"NO";
}
string to_string(const char* s) { 
	return string(s); }
string to_string(string s) { 
	return s; 
}
string to_string(vt<bool> v) { 
	string res; 
	rp(i, sz(v)) 
		res+=char('0'+v[i]);  
	return res; 
}
template<size_t S> string to_string(bitset<S> b) { 
	string res; 
	rp(i, S)
		res+=char('0'+b[i]);
	return res; 
}
tcT> string to_string(pair<T, T> p) { 
	string res;
	res += to_string(p.first); 
	res += ' '; 
	res += to_string(p.second); 
	return res;
}
tcT> string to_string(vt<T> & v) { 
	bool f=1; 
	string res; 
	for (auto& x: v) { 
		if(!f) 
			res+=' ';
		f=0; 
		res+=to_string(x);
	} 
	return res;
}
template<class A> void write(A x) { 
	cout << to_string(x); 
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h); 
	write(t...); 
}
void print() { 
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h); 
	if(sizeof...(t)) 
		write(' '); 
	print(t...);
}
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...);
}
#define wr write
#define ps print
// ------ ------ ------ alg ------ ------ ------ //
tcTU> void sort(vt<T> & a, U f) { 
	sort(a.begin(), a.end(), f); 
}
tcT> void rsor(vt<T> & a) { 
	sort(a.begin(), a.end(), greater<T>()); 
}
void rsor(str & a) { 
	sort(a.begin(), a.end(), greater<char>()); 
}
tcT> void rev(vt<T> & a){ 
	reverse(a.begin(), a.end()); 
}
void rev(str & a){ 
	reverse(a.begin(), a.end()); 
}

#define vmax(x) *max_element(begin(x), end(x))
#define vmin(x) *min_element(begin(x), end(x))
#define umax(x, n) *max_element((x), (x) + (n))
#define umin(x, n) *min_element((x), (x) + (n))

tcT> bool amin(T & a, const T & b) {
	return b<a?a=b, 1:0;
}

tcT> bool amax(T & a, const T & b) {
	return a<b?a=b, 1:0;
}

tcT> T cdiv(T a, T b) {return (a+b-1)/b;} 
 
tcTU> T ftrue(T lo, T hi, U f) { 
	while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } 
	return lo;
}
tcTU> T ltrue(T lo, T hi, U f) {
	while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } 
	return lo;
}

#define ri(...) int __VA_ARGS__; re(__VA_ARGS__);
#define rl(...) ll __VA_ARGS__; re(__VA_ARGS__);
#define rs(...) str __VA_ARGS__; re(__VA_ARGS__);

const int mxn = 2e5 + 10; 
const int inf = 1e9 + 10; 
const int M = 1e9 + 7; 

struct DSU {
    vector<int> e, f;
    DSU(int N) { e = vector<int>(N, -1);  f = vector<int>(N, 0); }

    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool same(int a, int b) { return get(a) == get(b); }

    int size(int x) { return -e[get(x)]; }

    bool unite(int x, int y) {  
        x = get(x), y = get(y);
        if (x == y) {
        	f[x]++; return false; }
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x;
        f[x] += f[y] + 1; 
        // z.x = op(z.x, z.y); 
        return true;
    }
};


void solve() {
	ri(n, m); 
	DSU d(n); 
	rp(i, m) {
		int a, c; 
		char b, dd; 
		re(a, b, c, dd); 
		d.unite(--a, --c); 
	}
	set<int> st; 
	rp(i, n) st.ins(d.get(i)); 
	int cnt = 0; 
	for (auto u: st) cnt += d.size(u) == d.f[u]; 
	ps(cnt, sz(st)-cnt); 
	return;
}

int main() {
	quick; 

	int t = 1; 
	// cin >> t; 
	while (t--) solve(); 

	return 0; 
}

/* 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
*/

// you should actually read the stuff at the bottom

 

Submission Info

Compile Error

./Main.cpp: In function ‘std::string to_string(std::vector<bool>)’:
./Main.cpp:50:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   50 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:121:2: note: in expansion of macro ‘rp’
  121 |  rp(i, sz(v))
      |  ^~
./Main.cpp: In function ‘std::string to_string(std::bitset<_Nb>)’:
./Main.cpp:50:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   50 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:127:2: note: in expansion of macro ‘rp’
  127 |  rp(i, S)
      |  ^~
./Main.cpp: In function ‘void solve()’:
./Main.cpp:50:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   50 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:251:2: note: in expansion of macro ‘rp’
  251 |  rp(i, m) {
      |  ^~
./Main.cpp:50:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   50 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:258:2: note: in expansion of macro ‘rp’
  258 |  rp(i, n) st.ins(d.get(i));
      |  ^~

Judge Result