TLE on #13求调
查看原帖
TLE on #13求调
716260
SegmentTree_楼主2024/7/19 11:27
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define lid (id << 1)
#define rid (id << 1 | 1)
const int N = 2e5+5;
namespace io {
	#define fastio ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
//    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	#define gc() getchar() 
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
    inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    template <class I> inline void read(I &x){ for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f; }
    template <class I> inline void write(I x) { if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x; while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) putc (qu[qr --]); }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::read;
using io::write;
using io::putc;
namespace tianyu{
	int n, m, q;
	int head[N], nxt[N], to[N], cccnnnttt;
	int block[N], bcnt;
	int scc[N], scctot;
	int dfn[N], low[N], dfncnt;
	bool vis[N];
	int ax[N], ay[N];
	int fa[N][21], dep[N];
	int a[N], b[N];
	bool gb[N];
	void add(int u, int v){
		nxt[++cccnnnttt] = head[u];
		to[cccnnnttt] = v;
		head[u] = cccnnnttt;
	}
	void tarjan(int u, int f){
		dfn[u] = low[u] = ++dfncnt;
		for (int i = head[u];i;i = nxt[i]){
			int v = to[i];
			if (v == f) continue;
			if (!dfn[v]){
				tarjan(v, u);
				low[u] = min(low[u], low[v]);
				if (low[v] > dfn[u]) gb[i] = gb[i + (i & 1 ? 1 : -1)] = 1;
			}
			else{
				low[u] = min(low[u], dfn[v]);
			}
		}
	}
	void dfs(int u){
		vis[u] = 1;
		scc[u] = scctot;
		for (int i = head[u];i;i = nxt[i]){
			if (gb[i]) continue;
			int v = to[i];
			if (vis[v]) continue;
			dfs(v);
		}
	}
	void dfs1(int u, int f){
		block[u] = bcnt;
		dep[u] = dep[f] + 1;
		fa[u][0] = f;
		for (int i = 1;i <= 17;i++){
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
		for (int i = head[u];i;i = nxt[i]){
			int v = to[i];
			if (v == f) continue;
			dfs1(v, u);
		}
	}
	int LCA(int u, int v){
		if (dep[u] < dep[v]) swap(u, v);
		for (int i = 17;i >= 0;i--){
			if (dep[fa[u][i]] >= dep[v]){
				u = fa[u][i];
			}
		}
		if (u == v) return u;
		for (int i = 17;i >= 0;i--){
			if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
		}
		return fa[u][0];
	}
	bool gans(int u, int f){
		for (int i = head[u];i;i = nxt[i]){
			int v = to[i];
			if (v == f) continue;
			if (!gans(v, u) || (a[v] && b[v])) return 0;
			a[u] += a[v];
			b[u] += b[v]; 
		}
		return 1;
	}
	void awa(){
		 read(n), read(m), read(q);
		 for (int i = 1;i <= m;i++){
		 	int u, v;
		 	read(u), read(v);
		 	ax[i] = u, ay[i] = v;
		 	add(u, v);
		 	add(v, u);
		 } 
		 for (int i = 1;i <= n;i++) if (!dfn[i]) tarjan(i, 0);
		 for (int i = 1;i <= n;i++){
		 	if (!scc[i]){
		 		++scctot;
		 		dfs(i);
		 	}
		 }
		 memset(head, 0, sizeof head);
		 cccnnnttt = 0;
		 for (int i = 1;i <= m;i++){
		 	 if (scc[ax[i]] != scc[ay[i]]){
		 		 add(scc[ax[i]], scc[ay[i]]);
		 		 add(scc[ay[i]], scc[ax[i]]);
		 	 }
		 }
		 for (int i = 1;i <= scctot;i++){
		 	 if (!block[i]){
		 	 	 ++bcnt;
				 dfs1(i, 0);
			 }
		 }
		 for (int i = 1;i <= q;i++){
			int s, t;
			read(s), read(t);
			s = scc[s], t = scc[t];
			if (s == t) continue;
			if (block[s] != block[t]){
				cout << "No";
				return;
			}
			int lca = LCA(s, t);
			++a[s], ++b[t];
			--a[lca], --b[lca];
		 }
		 for (int i = 1;i <= n;i++){
	 		if (!gans(i, 0) && !fa[i][0]){
	 			cout << "No";
	 			return;
	 		}
		 }
		 cout << "Yes";
	}
}
signed main(){ 
//	fastio;
	int T = 1;
	while (T--){
		tianyu::awa();
	}
	return 0;
}```
2024/7/19 11:27
加载中...