Submission #1174006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174006		LucaIlie	File Paths (BOI15_fil)	C++20	33 / 100	11 ms	4168 KiB

fil

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 8e3 + 1;
const int MAX_LEN = 4e6;
int n, m, 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 ) {
    //if ( u == 3007 )
    //    printf( "%d %d\n", u, depth[u] );
    if ( u <= n )
        nonCycleLens[depth[u] + s]++;
    for ( int v: adj[u] ) {
        depth[v] = depth[u] + val[v];
        dfs( v );
    }
}

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

    for ( int v: ancestors ) {
        if ( nonCycleLens[k - depth[u] + depth[v]] > 0 )
            ans[u] = true;
        //ans[u] |= (nonCycleLens[k - depth[u] + depth[v]] > 0); 
    }
    /*int c = k - depth[u];
    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 );

    if ( u <= n ) {
        /*for ( int v: ancestors )
            cycleLens[depth[u] - depth[v] + s]--;
        */
        ancestors.pop_back();
    }
}

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

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

    for ( int v = 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: 33 / 33
• Subtask 3: 0 / 34