40pts WA #1 #3 #4求条
查看原帖
40pts WA #1 #3 #4求条
716260
SegmentTree_楼主2024/8/15 16:53
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define i128 __int128
#define mem(x, y) memset(x, y, sizeof x)
#define lid (id << 1)
#define rid (id << 1 | 1)
#define fin(x) freopen(#x".in", "r", stdin)
#define fout(x) freopen(#x".out", "w", stdout)
const int N = 1e4+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;
    #ifdef ONLINE_JUDGE
    	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    #else
    	#define gc() getchar()
    #endif
    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; }
    inline void read(string &s) {s = "";char ch = gc();while (ch == ' ' || ch == '\n' || ch == '\r') ch = gc();while (ch != ' ' && ch != '\n' && ch != '\r') s += ch, ch = gc();}
    inline void read(char &ch) { ch = gc(); while (ch < 'A' || ch > 'z' || (ch > 'Z' && ch < 'a')) ch = gc(); }
    template <typename T, typename TT> inline void read(pair<T, TT> &a){read(a.first);read(a.second);}
    template <typename T, typename... Args> inline void read(T &num, Args &...args) { read(num), read(args...); }
    template <class I> inline void wr(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 --]); }
    template <> inline void wr(string ch) {for (char c : ch) putc(c);}
    template <> inline void wr(const char* ch) {wr(string(ch));}
    template <> inline void wr(char ch){ putc(ch); }
    template <typename T, typename TT> inline void wr(pair<T, TT> a, char _sep){wr(a.first);wr(_sep);wr(a.second);}
    inline void wr1(){ wr('\n'); }
    inline void wr2(){ ; }
    template <typename T, typename... Args> inline void wr1(T num, Args... args) {wr(num), wr(' '), wr1(args...) ;}
    template <typename T, typename... Args> inline void wr2(T num, Args... args) {wr(num), wr('\n'), wr2(args...) ;}
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::read;
using io::wr;
using io::wr1;
using io::wr2;
namespace tianyu{
	mt19937 rd(time(0));
	int n, q;
	int que[105];
	bool ans[105];
	int head[N], nxt[N << 1], to[N << 1], cst[N << 1], cccnnnttt;
	int dep[N], anod[N], btr[N], ndtot, siz[N], mxsiz[N];
	bool vis[N];
	void add(int u, int v, int w){
		to[++cccnnnttt] = v;
		cst[cccnnnttt] = w;
		nxt[cccnnnttt] = head[u];
		head[u] = cccnnnttt;
	}
	void getroot(int u, int f, int total, int &ct){
		siz[u] = 1;
		mxsiz[u] = 0;
		for (int i = head[u];i;i = nxt[i]){
			int v = to[i];
			if (v == f || vis[v]) continue;
			getroot(v, u, total, ct);
			siz[u] += siz[v];
			mxsiz[u] = max(mxsiz[u], siz[v]);
		}
		mxsiz[u] = max(mxsiz[u], total - siz[u]);
		if (mxsiz[u] <= total / 2) ct = u;
	}
	void getdis(int u, int f, int dis, int tre){
		anod[++ndtot] = u;
		dep[u] = dis;
		btr[u] = tre;
		for (int i = head[u];i;i = nxt[i]){
			int v = to[i];
			if (v == f || vis[v]) continue;
			getdis(v, u, dis + cst[i], tre);
		}
	}
	void dfz(int u = 1, int total = n){
		int root;
		getroot(u, 0, total, root);
		vis[root] = 1;
		anod[ndtot = 1] = root;
		dep[root] = 0;
		btr[root] = root;
		for (int i = head[root];i;i = nxt[i]){
			int v = to[i];
			if (vis[v]) continue;
			getdis(v, root, cst[i], v);
		}
		sort(anod + 1, anod + 1 + ndtot, [](int a, int b){return dep[a] < dep[b];});
		for (int i = 1;i <= q;i++){
			if (ans[i] || !que[i]) continue;
			int l = 1, r = ndtot;
			while (l < r){
				if (dep[anod[l]] + dep[anod[r]] > que[i]) --r;
				else if (dep[anod[l]] + dep[anod[r]] < que[i]) ++l;
				else if (btr[anod[l]] == btr[anod[r]]){if (dep[anod[r]] == dep[anod[r - 1]]) --r; else ++l;}
				else{ans[i] = 1;break;}
			}
		}
		for (int i = head[root];i;i = nxt[i]){
			int v = to[i];
			if (vis[v]) continue;
			dfz(v, siz[v]);
		}
	}
	void awa(){
		cin >> n >> q;
		for (int i = 1;i < n;i++){
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
			add(v, u, w);
		}
		for (int i = 1;i <= q;i++) cin >> que[i];
		dfz();
		for (int i = 1;i <= q;i++){
			cout << ((ans[i]) ? "AYE" : "NAY") << '\n';
		}
	}
}
_Atomic_word main(){ 
	fastio;
	int T = 1;
	while (T--){
		tianyu::awa();
	}
	return EXIT_SUCCESS;
}
2024/8/15 16:53
加载中...