이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/******************************************************
| '_ \ / _` |/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | (__| | | | | | (_| | | | |
| .__/ \__,_|\___|_| |_| |_|\__,_|_| |_|
|_|
__| |____________________________________________
,--. ,--. ,--. ,--.
|oo | _ \ `. | oo | | oo|
o o|~~ |(_) / ; | ~~ | | ~~|o o o o o
|/\/\| '._,' |/\/\| |/\/\|
__________________ ____________________________
******************************************************/
#include <bits/stdc++.h>
#define db(x) cerr << #x << ": " << x << endl
#define print cerr << "Ah shit, here we go again" << endl
#define int long long int
#define vii vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define ff first
#define ss second
#define mp make_pair
#define mod 1000000007
using namespace std;
const int maxn = 100;
int n, m, k;
struct mive {
int v, d, w;
};
int st[maxn], fn[maxn], timer;
vector<int> adj[maxn];
vector<mive> f;
void dfs(int v, int mpar = 0) {
st[v] = timer++;
for(auto u : adj[v]) {
if(u != mpar){
dfs(u, v);
}
}
fn[v] = timer++;
}
bool zird(int u, int v){
return st[u] >= st[v] and fn[u] <= fn[v];
}
void solve(){
cin >> n >> m >> k;
for(int i =1; i<=n; i++) adj[i].clear();
f.clear();
timer = 1;
for(int i =2; i<=n; i++){
int x;
cin >> x;
adj[x].push_back(i);
adj[i].push_back(x);
}
for(int i=0; i<m; i++){
int x, y, z;
cin >> x >> y >> z;
f.push_back({x, y, z});
}
dfs(1);
vector<int> v(m, 0);
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
if(i != j){
if(zird(f[j].v, f[i].v) and f[j].d < f[i].d){
v[i] |= (1 << j);
}
if(zird(f[i].v, f[j].v) and f[i].d < f[j].d){
v[i] |= (1 << j);
}
}
}
}
int ans = 0;
for(int mask =0; mask<(1<<m); mask++){
bool valid = true;
for(int i=0; i<m and valid; i++) if(mask & (1<<i)){
if(v[i] & mask){
valid = false;
}
}
if(valid){
ans = max(ans, (int)__builtin_popcount(mask));
}
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t =1;
while(t--){
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |