oj.uz

Submission #282019

# Submission time Handle Problem Language Result Execution time Memory
282019 2020-08-23T19:36:09 Z thecodingwizard File Paths (BOI15_fil) C++11
0 / 100
 1000 ms 4400 KB 
#include <bits/stdc++.h>

using namespace std;

// Case 1: exact length
// Case 2: some prefix of directories + symlink + some suffix to file
// Case 3: dist to file + constant*(place symlink in a parent directory of file)

int n, m, k, s; 
int dirLen[3001];
vector<int> subdirs[3001];
vector<int> dirfiles[3001];
int fileLen[3001];
bool ans[3001];
set<int> prefixLengths;

void dfsPrefixes(int u, int d) {
    prefixLengths.insert(d);
    for (int dir : subdirs[u]) {
        dfsPrefixes(dir, d + dirLen[dir]);
    }
}

vector<int> prefixLenStack;
int numCaseThreeLengths[1000001];

void dfsCaseThree(int u, int d, int v) {
    if (d + s > 1000000) return;
    numCaseThreeLengths[d+s] += v;

    for (int sub : subdirs[u]) {
        dfsCaseThree(sub, d + dirLen[sub], v);
    }
}

void dfs(int u, int d) {
    prefixLenStack.push_back(d);

    dfsCaseThree(u, 0, 1);

    for (int f : dirfiles[u]) {
        int totLen = fileLen[f] + d;

        // case 1
        if (totLen == k) ans[f] = true;

        // case 2
        for (int pfx : prefixLenStack) {
            int suffix = d - pfx + s;
            int want = k - suffix;
            if (prefixLengths.count(want)) ans[f] = true;
        }

        // case 3
        int want = k - totLen;
        if (want > 0) {
            for (int i = 1; i <= want; i++) {
                if (want % i == 0 && numCaseThreeLengths[want/i] > 0) ans[f] = true;
            }
        }
    }

    for (int sub : subdirs[u]) {
        dfs(sub, d + dirLen[sub]);
    }

    dfsCaseThree(u, 0, -1);

    prefixLenStack.pop_back();
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> k >> s; s++;
    for (int i = 1; i <= n; i++) {
        int p, l; cin >> p >> l;
        dirLen[i] = l+1;
        subdirs[p].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int p, l; cin >> p >> l;
        fileLen[i] = l+1;
        dirfiles[p].push_back(i);
    }

    // generate prefixes
    dfsPrefixes(0, 0);

    dfs(0, 0);

    for (int i = 0; i < m; i++) {
        if (ans[i]) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
    
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 4400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -