| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 889710 |
2023-12-20T05:53:27 Z |
vjudge1 |
Council (JOI23_council) |
C++17 |
|
9 ms |
13660 KB |
#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);
}
}
}
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
council.cpp:126:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
126 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
13660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
