训练计划
作者:
目目目
,
2023-03-10 15:31:47
,
所有人可见
,
阅读 260
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 410, M = 2e5 + 10, INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
int p[N];
int start[N], ed[N];
int a[N];
int d[N];
vector<int> g[N];
int ans[N];
int q[N];
void solve()
{
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
start[i] = ed[p[i]] + 1;
ed[i] = start[i] + a[i] - 1;
}
bool fail = false;
for (int i = 1; i <= n; i++)
{
cout << start[i] << ' ';
if (start[i] + a[i] - 1 > m)
fail = true;
}
if (fail)
return;
for (int i = 1; i <= n; i++)
{
if (p[i])
{
g[i].push_back(p[i]);
d[p[i]]++;
}
}
memset(ans, 0x3f, sizeof ans);
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
if (!d[i])
{
q[++tt] = i;
ans[i] = m - a[i] + 1;
}
while (hh <= tt)
{
int t = q[hh++];
for (int j : g[t])
{
ans[j] = min(ans[j], ans[t] - a[j]);
if (--d[j] == 0)
q[++tt] = j;
}
}
cout << endl;
for (int i = 1; i <= n; i++)
cout << ans[i] << ' ';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// int T;
// cin >> T;
// while (T--)
solve();
return 0;
}