oj.uz

Submission #1021952

# Submission time Handle Problem Language Result Execution time Memory
1021952 2024-07-13T08:09:37 Z guagua0407 File Paths (BOI15_fil) C++17
100 / 100
 145 ms 52656 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e6+5;
vector<int> adj[mxn];
vector<ll> pre;
vector<int> p;
vector<int> l;
vector<int> ans;
int len;
int n,m,k;
vector<int> st;
vector<vector<int>> cand;
vector<int> cnt(mxn);

void dfs(int v){
    st.push_back(v);
    if(v<=n){
        for(auto u:st){
            cand[u].push_back(pre[v]+len-pre[u]);
        }
    }
    for(auto u:adj[v]){
        dfs(u);
    }
    st.pop_back();
}

void dfs2(int v){
    if(v<=n){
        for(auto x:cand[v]){
            if(x<mxn) cnt[x]++;
        }
    }
    else{
        int target=k-pre[v];
        if(target>0){
            for(int i=1;i*i<=target;i++){
                if(target%i==0){
                    if(cnt[i] or cnt[target/i]){
                        ans[v-n-1]=1;
                        break;
                    }
                }
            }
        }
    }
    for(auto u:adj[v]){
        dfs2(u);
    }
    if(v<=n){
        for(auto x:cand[v]){
            if(x<mxn) cnt[x]--;
        }
    }
}

int main() {_
    cin>>n>>m>>k;
    cin>>len;
    len++;
    pre.resize(n+m+1);
    p.resize(n+m+1);
    l.resize(n+m+1);
    for(int i=1;i<=n+m;i++){
        cin>>p[i]>>l[i];
        pre[i]=pre[p[i]]+l[i]+1;
    }
    for(int i=1;i<=n+m;i++){
        adj[p[i]].push_back(i);
    }
    ans.resize(m);
    cand.resize(n+1);
    dfs(0);
    dfs2(0);
    vector<ll> vec(n+1);
    for(int i=0;i<=n;i++){
        vec[i]=pre[i]+len;
    }
    vec.push_back(0);
    sort(all(vec));
    for(int i=0;i<m;i++){
        int pp=p[n+1+i],L=l[n+1+i];
        int cur=pre[pp]+L+1;
        bool tf=false;
        while(true){
            ll target=k-(cur-pre[pp]);
            int pos=lower_bound(all(vec),target)-vec.begin();
            if(pos!=n+1 and vec[pos]==target){
                tf=true;
            }
            if(tf or pp==0) break;
            pp=p[pp];
        }
        if(tf){
            ans[i]=1;
        }
    }
    for(int i=0;i<m;i++){
        cout<<(ans[i]?"YES":"NO")<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message

fil.cpp: In function 'void setIO(std::string)':
fil.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27740 KB Output is correct
2 Correct 11 ms 27836 KB Output is correct
3 Correct 11 ms 27740 KB Output is correct
4 Correct 13 ms 28252 KB Output is correct
5 Correct 13 ms 27992 KB Output is correct
6 Correct 12 ms 27876 KB Output is correct
7 Correct 17 ms 28504 KB Output is correct
8 Correct 12 ms 27740 KB Output is correct
9 Correct 12 ms 27740 KB Output is correct
10 Correct 11 ms 27780 KB Output is correct
11 Correct 14 ms 27996 KB Output is correct
12 Correct 13 ms 28248 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28248 KB Output is correct
2 Correct 15 ms 28248 KB Output is correct
3 Correct 15 ms 28252 KB Output is correct
4 Correct 15 ms 28252 KB Output is correct
5 Correct 82 ms 48200 KB Output is correct
6 Correct 75 ms 48208 KB Output is correct
7 Correct 48 ms 39056 KB Output is correct
8 Correct 61 ms 39000 KB Output is correct
9 Correct 16 ms 28252 KB Output is correct
10 Correct 18 ms 28212 KB Output is correct
11 Correct 14 ms 28764 KB Output is correct
12 Correct 72 ms 47592 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27740 KB Output is correct
2 Correct 11 ms 27836 KB Output is correct
3 Correct 11 ms 27740 KB Output is correct
4 Correct 13 ms 28252 KB Output is correct
5 Correct 13 ms 27992 KB Output is correct
6 Correct 12 ms 27876 KB Output is correct
7 Correct 17 ms 28504 KB Output is correct
8 Correct 12 ms 27740 KB Output is correct
9 Correct 12 ms 27740 KB Output is correct
10 Correct 11 ms 27780 KB Output is correct
11 Correct 14 ms 27996 KB Output is correct
12 Correct 13 ms 28248 KB Output is correct
13 Correct 15 ms 28248 KB Output is correct
14 Correct 15 ms 28248 KB Output is correct
15 Correct 15 ms 28252 KB Output is correct
16 Correct 15 ms 28252 KB Output is correct
17 Correct 82 ms 48200 KB Output is correct
18 Correct 75 ms 48208 KB Output is correct
19 Correct 48 ms 39056 KB Output is correct
20 Correct 61 ms 39000 KB Output is correct
21 Correct 16 ms 28252 KB Output is correct
22 Correct 18 ms 28212 KB Output is correct
23 Correct 14 ms 28764 KB Output is correct
24 Correct 72 ms 47592 KB Output is correct
25 Correct 15 ms 28248 KB Output is correct
26 Correct 15 ms 28240 KB Output is correct
27 Correct 14 ms 28136 KB Output is correct
28 Correct 14 ms 28252 KB Output is correct
29 Correct 88 ms 48184 KB Output is correct
30 Correct 79 ms 48308 KB Output is correct
31 Correct 51 ms 39004 KB Output is correct
32 Correct 48 ms 38896 KB Output is correct
33 Correct 18 ms 28248 KB Output is correct
34 Correct 14 ms 28252 KB Output is correct
35 Correct 16 ms 28764 KB Output is correct
36 Correct 145 ms 52656 KB Output is correct