Submission #889707

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889707	2023-12-20T05:52:22 Z	vjudge1	Tourism (JOI23_tourism)	C++17	0 / 100	189 ms	61012 KB

tourism

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 2e5+50, inf = 1e18, mod = 1e9+7;
vi g[N];
set<pii> mp, jol;
set<int> chk;
vii tod;
void dfs(int pos, int pr){
	if(chk.empty())return;
	if(chk.count(pos) > 0){
		chk.erase(chk.find(pos));
		if(!jol.empty()){
			for(auto i:jol){
				if(mp.count(i))tod.pb(i);
				mp.insert(i);
			}
			jol.clear();
		}
	}
	if(chk.empty())return;
	for(auto i:jol)cout << i.ff << ' ' << i.ss << '\n';
	cout << "____ " << pos << '\n';
	for(auto to:g[pos]){
		if(to == pr)continue;
		jol.insert({pos, to});
		dfs(to, pos);
		jol.erase(jol.find({pos, to}));
	}
}
int st[17][N];
int st2[17][N];
int get(int l, int r) {
    int cl = __lg(r - l + 1);
    return min(st[cl][l], st[cl][r - (1 << cl) + 1]);
}
int getm(int l, int r) {
    int cl = __lg(r - l + 1);
    return max(st2[cl][l], st2[cl][r - (1 << cl) + 1]);
}
void solve(){
	int n, m, q, a, b;
	cin >> n >> m >> q;
	bool ok = 1;
	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
		if(a!=i+1 && b!=i+2)ok = 0;
	}
	int pl[m+1]{};
	for(int i = 1; i <= m; i++){
		cin >> pl[i];
	}
	if(ok){
		for(int i = 1; i <= m; i++){
			st[0][i] = pl[i];
			st2[0][i] = pl[i];
		}
		for (int i = 1; i <= __lg(n); i++) {
			int len = 1 << (i - 1);
			for (int j = 1; j <= n; j++) {
				st[i][j] = min(st[i - 1][j], st[i - 1][ min(j + len, n) ]);
			}
		}
		for (int i = 1; i <= __lg(n); i++) {
			int len = 1 << (i - 1);
			for (int j = 1; j <= n; j++) {
				st2[i][j] = max(st2[i - 1][j], st2[i - 1][ min(j + len, n) ]);
			}
		}
		while(q--){
			int l, r;
			cin >> l >> r;
			cout << getm(l, r) - get(l, r)+1 << '\n';
		}
	}else{
		while(q--){
			int l, r;
			cin >> l >> r;
			for(int i = l+1; i <= r; i++)chk.insert(pl[i]);
			dfs(pl[l], -1);
			cout << mp.size()+1 << '\n';
			mp.clear();
			//~ queue<pii> q;
			//~ q.push({pl[l], 0});
			//~ int us[n+1]{};
			//~ while(!q.empty()){
				//~ auto [pos, ds] = q.front();
				//~ cout << pos << ' ' << ds << '\n';
				//~ q.pop();
				//~ us[pos] = 1;
				//~ for(auto to:g[pos]){
					//~ if(us[to])continue;
					//~ if(chk.count(to)){
						//~ ans += ds+1;
						//~ ds = 0;
					//~ }
				//~ }
				//~ for(auto to:g[pos]){
					//~ if(us[to])continue;
					
					//~ if(chk.count(to)){
						//~ chk.erase(to);
						//~ q.push({to, 0});
					//~ }else q.push({to, ds+1});
				//~ }
				//~ if(chk.empty())break;
			//~ }
			//~ cout << ans+1 << '\n';
		}
	}
}
main(){
	//~ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

tourism.cpp:130:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  130 | main(){
      | ^~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	16988 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	16988 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	21084 KB	Output is correct
2	Correct	2 ms	8884 KB	Output is correct
3	Correct	5 ms	9052 KB	Output is correct
4	Incorrect	189 ms	61012 KB	Output isn't correct
5	Halted	0 ms	0 KB	-