/ Randle /

记录详情

Runtime Error

/in/foo.cc:25:1: warning: multi-line comment [-Wcomment]
 // #define getchar()                                                         \
 ^
# 状态 耗时 内存占用
#1 Accepted 1ms 504.0 KiB
#2 Accepted 1ms 348.0 KiB
#3 Accepted 1ms 376.0 KiB
#4 Accepted 1ms 504.0 KiB
#5 Accepted 1ms 468.0 KiB
#6 Accepted 1ms 476.0 KiB
#7 Accepted 8ms 2.469 MiB
#8 Accepted 81ms 20.328 MiB
#9 Accepted 4ms 1.613 MiB
#10 Accepted 23ms 9.824 MiB
#11 Accepted 43ms 18.07 MiB
#12 Accepted 58ms 23.988 MiB
#13 Accepted 24ms 10.059 MiB
#14 Runtime Error 30ms 14.391 MiB
#15 Runtime Error 41ms 16.695 MiB
#16 Runtime Error 54ms 18.965 MiB
#17 Accepted 87ms 22.621 MiB
#18 Accepted 89ms 22.074 MiB
#19 Accepted 90ms 21.734 MiB
#20 Accepted 91ms 26.461 MiB

代码

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define pii pair<int, int>
#define il inline
#define p_q priority_queue
#define map unordered_map
#define rg register

using namespace std;

const int N1 = 100005;
const int N2 = 1000006;
const int mod = 1e8+7;



namespace first_coming {
#define IOSIZE 100000
	int precision = 3, POW[10] = {1,      10,      100,      1000,      10000,
		100000, 1000000, 10000000, 100000000, 1000000000
	};
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
// #ifdef ONLINE_JUDGE
// #define getchar()                                                         \
//     ((p1 == p2) and                                                       \
//              (p2 = (p1 = ibuf) + fread(ibuf, 1, IOSIZE, stdin), p1 == p2) \
//          ? (EOF)                                                          \
// : (*p1++))
// #define putchar(x)
//     ((p3 == obuf + IOSIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf),
//      *p3++ = x)
// #define isdigit(ch) (ch > 47 && ch < 58)
// #define isspace(ch) (ch < 33)
// #endif
	template <typename T>
	inline T read() {
		T s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) && (ch != EOF))
			if (ch == 45)
				w = -1;
		if (ch == EOF)
			return 0;
		while (isdigit(ch))
			s = s * 10 + ch - 48, ch = getchar();
		return s * w;
	}
	template <typename T>
	inline bool read(T& s) {
		s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) && (ch != EOF))
			if (ch == 45)
				w = -1;
		if (ch == EOF)
			return 0;
		while (isdigit(ch))
			s = s * 10 + ch - 48, ch = getchar();
		return s *= w, 1;
	}
	inline bool read(char& s) {
		while (s = getchar(), isspace(s))
			;
		return 1;
	}
	inline bool read(char* s) {
		char ch;
		while (ch = getchar(), isspace(ch))
			;
		if (ch == EOF)
			return 0;
		while (!isspace(ch))
			*s++ = ch, ch = getchar();
		*s = '\000';
		return 1;
	}
	template <typename T>
	inline void print(T x) {
		if (x < 0)
			putchar(45), x = -x;
		if (x > 9)
			print(x / 10);
		putchar(x % 10 + 48);
	}
	inline void print(char x) {
		putchar(x);
	}
	inline void print(char* x) {
		while (*x)
			putchar(*x++);
	}
	inline void print(const char* x) {
		for (int i = 0; x[i]; i++)
			putchar(x[i]);
	}
	inline bool read(std::string& s) {
		s = "";
		char ch;
		while (ch = getchar(), isspace(ch))
			;
		if (ch == EOF)
			return 0;
		while (!isspace(ch))
			s += ch, ch = getchar();
		return 1;
	}
	inline void print(std::string x) {
		for (int i = 0, n = x.size(); i < n; i++)
			putchar(x[i]);
	}
	inline bool read(bool& b) {
		char ch;
		while (ch = getchar(), isspace(ch))
			;
		b = ch ^ 48;
		return 1;
	}
	inline void print(bool b) {
		putchar(b + 48);
	}
	inline bool read(double& x) {
		int a = 0, b = 0;
		char ch = getchar();
		bool f = 0;
		while (ch < 48 || ch > 57) {
			if (ch == 45)
				f = 1;
			ch = getchar();
		}
		while (47 < ch && ch < 58) {
			a = (a << 1) + (a << 3) + (ch ^ 48);
			ch = getchar();
		}
		if (ch != 46) {
			x = f ? -a : a;
			return 1;
		}
		ch = getchar();
		while (47 < ch && ch < 58) {
			b = (b << 1) + (b << 3) + (ch ^ 48), ch = getchar();
		}
		x = b;
		while (x > 1)        x /= 10;
		x /= 10;
		x = f ? -a - x : a + x;
		return 1;
	}
	inline void print(double x) {
		if (x < 0) {
			putchar(45), x = -x;
		}
		x = round((long double)x * POW[precision]) / POW[precision],
		print((long long)x), putchar(46), x -= (long long)(x);
		for (int i = 1; i <= precision; i++)
			x *= 10, putchar(x + 48), x -= (int)x;
	}
	template <typename T, typename... T1>
	inline int read(T& a, T1&... other) {
		return read(a) + read(other...);
	}
	template <typename T, typename... T1>
	inline void print(T a, T1... other) {
		print(a), print(other...);
	}
	struct Fast_IO {
		~Fast_IO() {
			fwrite(obuf, p3 - obuf, 1, stdout);
		}
	} io;
	template <typename T>
	Fast_IO& operator>>(Fast_IO& io, T& b) {
		return read(b), io;
	}
	template <typename T>
	Fast_IO& operator<<(Fast_IO& io, T b) {
		return print(b), io;
	}
}

namespace second_coming {
	int fac[N2] = {0};
	il void Cinit(int p) {
		fac[0] = 1;
		for (int i = 1; i < N2; i++) {
			fac[i] = fac[i - 1] * i % p;
		}
	}
	il int qpow(int a, int b, int p) {
		int ans = 1;
		while (b) {
			if (b & 1) {
				ans = ans * a % p;
			}
			a = a * a % p;
			b >>= 1;
		}
		return ans;
	}
	il int C(int n, int m, int p) {
		if (m > n || m < 0) {
			return 0;
		}
		return fac[n] * qpow(fac[m], p - 2, p) % p * qpow(fac[n - m], p - 2, p) % p;
	}
	il int Lucas(int n, int m, int p) {
		if (!m)
			return 1;
		return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
	}
	il int GCD(int n, int m, int p) {
		return __gcd(n, m) % p;
	}
	il int LCM(int n, int m, int p) {
		return n * m % p * qpow(GCD(n, m, p), p - 2, p) % p;
	}
}
using namespace first_coming;
using namespace second_coming;

#define debug 0
#define endl '\n'

int _test_ = 1;
struct node{
	int x,y;
}f[2*N1],b[2*N1];
struct Sol{
	int F,S,T;
}ans[N2*2];
int l[N1*2],neew[N1*2];
node mex(node x,node y){
	node ans;
	ans.x=max(x.x,y.x);
	ans.y=x.y;
	if(x.x<ans.x) ans.y=max(ans.y,x.y);
	if(y.x<ans.x) ans.y=max(ans.y,y.x);
	if(y.y<ans.x) ans.y=max(ans.y,y.y);
	return ans;
}
Sol Max(Sol x,Sol y){
	Sol ans;
	if(x.F>y.F){
		ans.F=x.F;
		ans.S=max(x.S,y.F);
		ans.T=x.T;
		if(x.S<ans.S) ans.T=max(ans.T,x.S);
		if(y.F<ans.S) ans.T=max(ans.T,y.F);
		if(y.S<ans.S) ans.T=max(ans.T,y.S);
		if(y.T<ans.T) ans.T=max(ans.T,y.T);
	}
	else{
		ans.F=y.F;
		ans.S=max(y.S,x.F);
		ans.T=y.T;
		if(y.S<ans.S) ans.T=max(ans.T,y.S);
		if(x.F<ans.S) ans.T=max(ans.T,x.F);
		if(x.S<ans.S) ans.T=max(ans.T,x.S);
		if(x.T<ans.T) ans.T=max(ans.T,x.T);
	}
	return ans;
}
int nn[2*N1],las[2*N1],in[2*N1],out[2*N1];
int dfn=0;
void dfs(int x){
	in[x]=dfn+1;
	dfn++;
	neew[dfn]=x;
	for(int i=las[x];i;i=nn[i]){
		dfs(i);
		ans[x]=Max(ans[x],ans[i]);
	}
	out[x]=dfn;
}
int n,q;
namespace third_coming {
	
	
	il void init() {
		cin>>n>>q;
		// cout<<"Helo word";
		for(int i=2;i<=n;i++){
			int x;
			cin>>x;
			nn[i]=las[x];
			las[x]=i;
		}
		for(int i=1;i<=n;i++){
			cin>>ans[i].F>>l[i];
			ans[i].S=(int)-1e9;
			ans[i].T=(int)-1e9;
		}
		dfs(1);
	}
	
	il void solve() {
		f[0]=b[n+1]={0,(int)-1e9};
		for(int i=1;i<=n;i++){
			f[i]=mex(f[i-1],{l[neew[i]],(int)-1e9});
		}
		for(int i=n;i>=0;i--){
			b[i]=mex(b[i+1],{l[neew[i]],(int)-1e9});
		}
		while(q--){
			int x;
			cin>>x;
			node k=mex(f[in[x]-1],b[out[x]+1]);
			Sol p=ans[x];
			if(p.S<0){
				cout<<0<<'\n';
			}
			else{
				if(p.S+k.x==p.F){
					cout<<max(p.S+k.y,p.T+k.x)<<'\n';
				}
				else cout<<min(p.S+k.x,p.F)<<'\n';
			}
		}
	}
	
	il void main() {
		init();
		solve();
	}
	
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef debug
	// freopen("prime.in", "r", stdin);
	// freopen("prime.out", "w", stdout);
#endif
	third_coming::main();
	return 0;
}

信息

递交者
类型
递交
题目
士兵训练(CQ直辖市noip模拟赛) T3
题目数据
下载
语言
C++
递交时间
2024-09-03 10:44:21
评测时间
2024-09-03 11:16:12
评测机
分数
85
总耗时
740ms
峰值内存
26.461 MiB