Submission #1206741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206741		eyadooz	Biochips (IZhO12_biochips)	C++20	20 / 100	2097 ms	17084 KiB

biochips

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <math.h>
#include <array>
#include <random>
#include <bitset>
#include <climits>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define endl '\n'
#define mod 1000000007
#define INF 0x3f3f3f3f
#define int long long

template <class x>
using ordered_set = tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>;

typedef pair<int, int> ipair;

static inline int read()
{
    int x = 0;char ch = getchar();
    while (ch < '0' || ch>'9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}

static inline void print(const int &x) {
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}

int wi[2000005];
vector<int> adj[200005];
set<int> b;
bool f=1;
void dfs(int x, int p=-1, int bad=0)
{
    if(b.find(x)!=b.end()&&bad)
    {
        f=0;
        // cout << x << " " << bad << endl;
    }

    if(b.find(x)!=b.end()) bad=1;
    for(auto i : adj[x]) 
    {
        if(i!=p) dfs(i, x, bad);
    }
}
signed main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n, m;

    cin >> n >> m;

    int r=0;
    for(int i = 1;i <= n;i++) 
    {
        int x, w;
        cin >> x >> w;
        if(x==0) r = i;
        else
        {
            adj[x].push_back(i);
            adj[i].push_back(x);
        }
        wi[i]=w;
    }

    vector<int> s;
    for(int i = 1;i <= n;i++) s.push_back(i);

    int ans=0;
    do
    {
        b.clear();
        f=1;
        for(int i = 0;i < m;i++) b.insert(s[i]);
        dfs(r);
        if(f)
        {
            int cnt=0;
            for(int i = 0;i < m;i++) cnt += wi[s[i]];
            ans=max(ans, cnt); 
        }
    }while(next_permutation(s.begin(), s.end()));

    cout << ans;
}
    

• Subtask 1: 20 / 100