萌新求卡常
查看原帖
萌新求卡常
436107
Creeper_l楼主2023/11/21 10:57

写的 33 loglog,有大佬过了,本菜鸡一直 TLE on #22,求卡常。

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std; 
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
    if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return '\n';
    }
    return *S++;
}
}
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
    fwrite(buf, 1, S - buf, stdout);
    S = buf;
}
inline void putchar(char c) {
    *S++ = c;
    if (S == T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename T>
    Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = getchar();
        }
        x *= f;
        return *this;
    }
    Reader& operator >> (char& c) {
        c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        return *this;
    }
    Reader& operator >> (char* str) {
        int len = 0;
        char c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
            str[len++] = c;
            c = getchar();
        }
        str[len] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename T>
    Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static int sta[45];
        int top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
    }
    Writer& operator << (char c) {
        putchar(c);
        return *this;
    }
    Writer& operator << (char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer& operator << (const char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer(){}
} cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define ls id << 1
#define rs id << 1 | 1
#define int long long
#define re register
typedef pair <int,int> pii;
const int MAXN = 1e5 + 10;
int n,L,R,head[MAXN],b[MAXN],cnt,x,y,z,ans,maxn = 0;
int pt,ansx,ansy,mi;
bool vis[MAXN],flag = false;
struct F{int u,num,dis;}p[MAXN]; 
struct Node{int u,v,w,nxt;}e[MAXN <<1],g[MAXN << 1];
struct SegmentTree{int l,r,mx,node;}tree[MAXN << 2];
inline void Add(int u,int v,int w){e[++cnt] = {u,v,w,head[u]};head[u] = cnt;}
inline int Get_size(int u,int father)
{
	if(vis[u] == true) return 0;
	re int sum = 1;
	for(re int i = head[u]; ~ i;i = e[i].nxt)
		if(e[i].v != father) sum += Get_size(e[i].v,u);
	return sum;
}
inline int Get_wc(int u,int father,int tot,int &wc)
{
	if(vis[u] == true) return 0;
	re int sum = 1,mx = 0;
	for(re int i = head[u]; ~ i;i = e[i].nxt)
	{
		re int now = e[i].v;
		if(now == father) continue;
		re int tmp = Get_wc(now,u,tot,wc);
		sum += tmp,mx = max(mx,tmp); 
	}
	if(max(mx,tot - sum) <= tot / 2) wc = u;
	return sum;
}
inline void Get_dist(int u,int father,int num,int dis)
{
	if(vis[u] == true) return;
	p[++pt] = {u,num,dis};
	for(re int i = head[u]; ~ i;i = e[i].nxt)
	{
		re int now = e[i].v;
		if(now == father) continue;
		Get_dist(now,u,num + 1,dis + (e[i].w >= mi ? 1 : -1));
	}
}
inline void Pushup(int id)
{
	if(tree[ls].mx > tree[rs].mx) tree[id].node = tree[ls].node;
	else tree[id].node = tree[rs].node;
	tree[id].mx = max(tree[ls].mx,tree[rs].mx);
}
inline void Build(int id,int l,int r)
{
	tree[id].l = l,tree[id].r = r,tree[id].mx = -1e9;
	tree[id].node = 0;
	if(l == r) return;
	re int mid = (l + r) >> 1;
	Build(ls,l,mid),Build(rs,mid + 1,r);
}
inline void Update(int id,int l,int r,int a,int b,int c)
{
	if(l == r)
	{
		if(b > tree[id].mx) tree[id].node = c;
		tree[id].mx = max(tree[id].mx,b);return;
	}
	re int mid = (l + r) >> 1;
	if(a <= mid) Update(ls,l,mid,a,b,c);
	else Update(rs,mid + 1,r,a,b,c);
	Pushup(id);
}
inline SegmentTree Query(int id,int l,int r,int a,int b)
{
	if(a <= l && b >= r) return tree[id];
	re int mid = (l + r) >> 1;
	if(a > mid) return Query(rs,mid + 1,r,a,b);
	if(b <= mid) return Query(ls,l,mid,a,b);
	SegmentTree FL = Query(ls,l,mid,a,b),FR = Query(rs,mid + 1,r,a,b),res;
	if(FL.mx > FR.mx) res.node = FL.node;
	else res.node = FR.node;
	res.mx = max(FL.mx,FR.mx);
	return res;
}
inline void calc(int u)
{
	if(vis[u] == true) return;
	Get_wc(u,0,Get_size(u,0),u);
	re int m = Get_size(u,0);vis[u] = true;
	Build(1,1,m);
	for(re int i = head[u]; ~ i;i = e[i].nxt)
	{
		re int now = e[i].v;
		pt = 0;
		Get_dist(now,u,1,e[i].w >= mi ? 1 : -1);
		for(re int j = 1;j <= pt;j = -~j)
		{
			re int num = p[j].num,dis = p[j].dis,node = p[j].u;
			if(num > R) continue;
			if(num >= L && dis >= 0){ansx = u,ansy = node;flag = true;return;}
			if(num == R) continue;
			int f = max(1ll,L - num),s = min(m,R - num);
			if(f > s)continue;
			SegmentTree tmp = Query(1,1,m,f,s);
			if(tmp.mx + dis >= 0 && tmp.node != 0){ansx = tmp.node,ansy = node;flag = true;return;}
		}
		for(re int j = 1;j <= pt;j = -~j)
		{
			re int num = p[j].num,dis = p[j].dis,node = p[j].u;
			Update(1,1,m,num,dis,node);
		}
	}
	for(re int i = head[u]; ~ i;i = e[i].nxt) calc(e[i].v);
}
inline bool check()
{
	for(re int i = 1;i <= n;i = -~i) vis[i] = false;
	flag = false,calc(1);
	if(flag == true) return true;
	else return false;
}
signed main()
{
	memset(head,-1,sizeof head);
	cin >> n >> L >> R;
	for(re int i = 1;i < n;i = -~i) cin >> x >> y >> z,Add(x,y,z),Add(y,x,z),b[i] = z;
	sort(b + 1,b + n);
	re int len = unique(b + 1,b + n) - b - 1;
	re int l = 1,r = len;
	while(l <= r)
	{
		re int mid = (l + r) >> 1;
		mi = b[mid];
		if(check()) l = mid + 1,ans = b[mid];
		else r = mid - 1;
	}
	cout << ansx << " " << ansy;
	return 0;
}
2023/11/21 10:57
加载中...