Submission #230729

#	Time	Username	Problem	Language	Result	Execution time	Memory
230729		emil_physmath	File Paths (BOI15_fil)	C++17	100 / 100	429 ms	976 KiB

fil

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <limits>
#include <vector>
#include <map>
using namespace std;
 
vector<int> chld[6001];
int tin[6001], tout[6001], p[6001], len[6001], depth[6001];
 
inline bool Upper(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
void DFS(int v)
{
    static int time = 0;
    tin[v] = ++time;
    for (int to: chld[v])
        DFS(to);
    tout[v] = time;
}
int main()
{
    int n, m, des;
    cin >> n >> m >> des;
    int sym;
    cin >> sym;
    ++sym;
    p[0] = -1;
    for (int i = 1; i <= n + m; ++i)
    {
        scanf("%d%d", &p[i], &len[i]);
        chld[p[i]].push_back(i);
        ++len[i];
        depth[i] = depth[p[i]] + len[i];
    }
    DFS(0);
    vector<int> pref; pref.reserve(n + m);
    vector<int> prefv; prefv.reserve(n + m);
    vector<int> stNodes;
    for (int i = 0; i <= n; ++i)
        stNodes.push_back(i);
    sort(stNodes.begin(), stNodes.end(), [](int u, int v) {
         return depth[u] < depth[v];
    });
    for (int i = n + 1; i <= n + m; ++i)
    {
        pref.clear(); prefv.clear();
        for (int j = i; j != -1; j = p[j])
        {
            prefv.push_back(j);
            pref.push_back(depth[j]);
        }
        reverse(pref.begin(), pref.end());
        reverse(prefv.begin(), prefv.end());
        bool ans = pref.back() == des;
        for (int from = 0; !ans && from <= n; ++from)
            if (binary_search(pref.begin(), prev(pref.end()), depth[from] + sym + pref.back() - des))
            {
                ans = true;
                break;
            }
        if (des - pref.back() > 0)
        {
            for (int x = 1; !ans && x * x <= des - pref.back(); ++x)
                for (int y = 0; !ans && y <= 1; ++y, x = (des - pref.back()) / x)
                {
                    if ((des - pref.back()) % x) continue;
                    int i = 0;
                    for (int from: stNodes)
                    {
                        // depth[from] - depth[to] + sym == x
                        // depth[to] = depth[from] + sym - x
                        while (i + 1 < pref.size() && pref[i + 1] <= depth[from] + sym - x)
                            ++i;
                        if (pref[i] != depth[from] + sym - x) continue;
                        if (Upper(prefv[i], from))
                        {
                            ans = true;
                            break;
                        }
                    }
                }
        }
        printf(ans ? "YES\n" : "NO\n");
    }
}

Compilation message (stderr)

fil.cpp: In function 'int main()':
fil.cpp:74:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         while (i + 1 < pref.size() && pref[i + 1] <= depth[from] + sym - x)
                                ~~~~~~^~~~~~~~~~~~~
fil.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &p[i], &len[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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