Submission #1173966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173966		LucaIlie	File Paths (BOI15_fil)	C++20	0 / 100	5 ms	7748 KiB

fil

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 6e3 + 1;
const int MAX_LEN = 2e6;
int k, s;
bool ans[MAX_N];
int val[MAX_N], depth[MAX_N], nonCycleLens[MAX_LEN + 1], cycleLens[MAX_LEN + 1];
vector<int> adj[MAX_N];

void dfs( int u ) {
    nonCycleLens[depth[u] + s]++;
    for ( int v: adj[u] ) {
        depth[v] = depth[u] + val[v];
        dfs( v );
    }
}

vector<int> ancestors;
void findAll( int u ) {
    ancestors.push_back( u );
    for ( int v: ancestors )
        cycleLens[depth[u] - depth[v] + s]++;

    for ( int v: ancestors ) {
        if ( u != v )
            ans[u] |= (nonCycleLens[k - depth[u] + depth[v]] > 0); 
    }
    /*for ( int d = 1; d * d <= c; d++ ) {
        if ( c % d == 0 ) {
            if ( cycleLens[d] || cycleLens[c / d] )
                ans[u] = true;
        }
    }*/

    for ( int v: adj[u] )
        findAll( v );

    for ( int v: ancestors )
        cycleLens[depth[u] - depth[v] + s]--;
    ancestors.pop_back();
}

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int n, m;

    cin >> n >> m >> k >> s;
    s++;

    for ( int v = 1; v <= n; v++ ) {
        int p;
        cin >> p >> val[v];
        adj[p].push_back( v );
        val[v]++;
    }

    for ( int v = n + 1; v <= n + m; v++ ) {
        int p;
        cin >> p >> val[v];
        adj[p].push_back( v );
        val[v]++;
    }

    nonCycleLens[0] = 1;
    dfs( 0 );
    findAll( 0 );

    for ( int i = n + 1; i <= n + m; i++ )
        cout << (ans[i] ? "YES\n" : "NO\n");

    return 0;
}

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