제출 #836132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836132		josanneo22	Tourism (JOI23_tourism)	C++17	17 / 100	3427 ms	28620 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define ar array

/*tourism
subtask 1&2: make root at l[i] then just find number of nodes passed through
subtask 3: since it is a chain, we just have to find max(c[l...r])-min(c[l...r])+1
*/
const int inf=1e18;
struct yl{
	int l,r,val;
};
struct seg_mx{
	vector<yl> tr;
	vector<int> C;
	seg_mx(){}
	seg_mx(int n,vector<int> &c){
		int S=4*n+600; C=c;
		tr.resize(S);
		build(1,1,n);
	}
	void build(int p,int l,int r){
		tr[p].l=l; tr[p].r=r;
		if(l==r){ tr[p].val=C[l]; return;}
		int mid=(l+r)>>1;
		build(p<<1,l,mid); build(p<<1|1,mid+1,r);
		tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
		return;
	}
	int query(int p,int l,int r){
		if(tr[p].l>r || tr[p].r<l) return -inf;
		if(l<=tr[p].l && tr[p].r<=r) return tr[p].val;
		return max(query(p<<1,l,r),query(p<<1|1,l,r));
	}
};

struct seg_mn{
	vector<yl> tr;
	vector<int> C;
	seg_mn(){}
	seg_mn(int n,vector<int> &c){
		int S=4*n+600; C=c;
		tr.resize(S);
		build(1,1,n);
	}
	void build(int p,int l,int r){
		tr[p].l=l; tr[p].r=r;
		if(l==r){ tr[p].val=C[l]; return;}
		int mid=(l+r)>>1;
		build(p<<1,l,mid); build(p<<1|1,mid+1,r);
		tr[p].val=min(tr[p<<1].val,tr[p<<1|1].val);
		return;
	}
	int query(int p,int l,int r){
		if(tr[p].l>r || tr[p].r<l) return inf;
		if(l<=tr[p].l && tr[p].r<=r) return tr[p].val;
		return min(query(p<<1,l,r),query(p<<1|1,l,r));
	}
};

void solve(){
	int n,m,q; cin>>n>>m>>q;
	int sub12=0;
	if(n*q<=2e8) sub12=1;
	vector<vector<int>> g(n+1);
	for(int i=0;i<n-1;i++){
		int u,v; cin>>u>>v;
		g[u].pb(v); g[v].pb(u);
	}
	vector<int> c(m+1),d(n+1);
	for(int i=1;i<=m;i++) cin>>c[i];
	seg_mx mx(m,c); 
	seg_mn mn(m,c);
	function<void(int,int)> dfs=[&](int u,int f){
		for(auto&v:g[u]){
			if(v==f) continue;
			dfs(v,u);
			d[u]+=d[v];
		}
	};
	auto reset=[&](int l,int r){
		for(int i=1;i<=n;i++) d[i]=0;
		for(int i=l;i<=r;i++) d[c[i]]=1;
	};
	auto ans2=[&](int l,int r){
		int rr=mx.query(1,l,r);
		int ll=mn.query(1,l,r);
		cout<<rr-ll+1<<'\n';
	};
	auto ans1=[&](int l,int r){
		reset(l,r);
		dfs(c[l],0);
		int rs=0;
		for(int i=1;i<=n;i++) if(d[i]>=1) rs++;
		cout<<rs<<'\n';
	};
	while(q--){
		int l,r; cin>>l>>r;
		if(sub12) ans1(l,r);
		else ans2(l,r);
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	clock_t tStart = clock();
	int local=0,multi=0,debug=1,tt=1;
	if(local){
	    freopen("input.txt","r",stdin);
	    freopen("output.txt","w",stdout);
	}	
	if(multi) cin>>tt;
	for(int i=1;i<=tt;i++){
		if(debug && multi && local) cout<<"样例 "<<i<<'\n';
		solve();
 	}
	fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp: In function 'int main()':
tourism.cpp:117:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |      freopen("input.txt","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:118:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |      freopen("output.txt","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41