Submission #1270580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270580		nathan4690	File Paths (BOI15_fil)	C++20	100 / 100	176 ms	5628 KiB

fil

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name "btoi15p4"
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

int n, m, k, s, p[maxn], len[maxn];
bool ok[maxn];
bool jmp[maxn];
int cyc[maxn];
vector<int> G[maxn];

void dfs1(int u, int totl){
    totl += len[u] + (u != 0);
    if(totl <= k && u <= n) {
        jmp[totl] = true;
//        cout << "! " << u << ' ' << totl << '\n';
    }
    for(int c: G[u]){
        if(c <= n){
            dfs1(c, totl);
        }
    }
}

void add(int u, int totl, int val){
//    totl += len[u] + (u != 0);
    if(u <= n){
//        if(val > 0) cerr << "+ " << u << ' ' << totl + s + 1 << '\n';
//        else cerr << "- " << u << ' ' << totl + s + 1 << '\n';
        if(totl + s + 1 <= k) cyc[totl + s + 1] += val;
    }
    for(int c: G[u]){
        add(c, totl + len[c] + 1, val);
    }
}

void dfs2(int u, int totl){
    totl += len[u] + (u != 0);
    if(u > n){
        if(totl == k) return void(ok[u - n] = 1);
        int v = u, clen = 0;
        while(v){
            clen += len[v] + 1;
//            if(u == n + 6) cerr << v << ' ' << len[v] + 1 << '\n';
            if(clen > k) break;
            if(jmp[k - clen]) return void(ok[u - n] = 1);
            v = p[v];
        }
        if(totl > k) return;
        int totcyc = k - totl;
//        if(u == n + 6){
//            cerr << totl << ' ' << totcyc << '\n';
//            f1(i, totcyc){
//                if(cyc[i]) cerr << "! " << i << '\n';
//            }
//        }
        for(int i=1;i*i<=totcyc;i++){
            if(totcyc % i == 0){
                if(cyc[i] || cyc[totcyc / i]) return void(ok[u - n] = 1);
            }
        }
        return;
    }
    add(u, 0, 1);
    for(int c: G[u]){
        dfs2(c, totl);
    }
    add(u, 0, -1);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> m >> k >> s;
    f1(i,n){
        int par, l; cin >> par >> l;
        p[i] = par;
        len[i] = l;
        G[par].push_back(i);
    }
    f1(i,m){
        int par, l; cin >> par >> l;
        p[i+n] = par;
        len[i+n] = l;
        G[par].push_back(i+n);
    }
    dfs1(0, s + 1);
    cyc[s + 1] = 1;
    dfs2(0, 0);
    f1(i,m) cout << (ok[i] ? "YES" : "NO") << '\n';
    return 0;
}

Compilation message (stderr)

fil.cpp: In function 'int main()':
fil.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34