Cod sursa(job #2015429)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 august 2017 03:30:50
Problema Tproc Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.04 kb
#include <bits/stdc++.h>
using namespace std;

fstream in("tproc.in", ios::in);
fstream out("tproc.out", ios::out);

const int DMAX = 4140;
const int MMAX = 500;
const int NMAX = 500;
const int KMAX = 8;

const int INF = 0x3f3f3f3f;

int pos[MMAX][NMAX], dp[MMAX][DMAX], aux[MMAX][DMAX];
int cst[NMAX][NMAX], whg[KMAX];

vector<int> edg[MMAX], lst[MMAX]; vector<vector<int>> msk[KMAX];
vector<pair<int, int>> prl[MMAX], cml[MMAX];

void back(vector<int> par, int l, int v, int k) {
    if (l == KMAX)
        return;
    
    par.push_back(0);
    for (int i = 0; i < min(v + 1, k); ++i) {
        par.back() = i;
        
        msk[l].push_back(par);
        back(par, l + 1, max(v, par.back() + 1), k);
    }
    
    return;
}

void dfs(int x, int f) {
    for (int i = 0; i < lst[x].size(); ++i)
    for (int j = i + 1; j < lst[x].size(); ++j)
        if (f == -1 or find(lst[f].begin(), lst[f].end(), lst[x][i]) == lst[f].end()
                    or find(lst[f].begin(), lst[f].end(), lst[x][j]) == lst[f].end())
            prl[x].push_back(make_pair(i, j));
    
    if (f != -1) {
        for (int p : lst[x])
            if (find(lst[f].begin(), lst[f].end(), p) != lst[f].end())
                cml[x].push_back(make_pair(
                    find(lst[f].begin(), lst[f].end(), p) - lst[f].begin(),
                    find(lst[x].begin(), lst[x].end(), p) - lst[x].begin()));
    }
    
    for (int y : edg[x])
        if (y != f) dfs(y, x);
    
    int sz1 = (int) lst[x].size() - 1;
    if (cml[x].size() == 0)
        aux[x][0] = INF;
    else
        memset(aux[x], INF, msk[cml[x].size() - 1].size() * 4);
    
    for (int cnf = 0; cnf < msk[sz1].size(); ++cnf) {
        for (int y : edg[x]) {
            if (y == f) continue;
            
            vector<int> arr; int ps = 0;
            int sz2 = (int) cml[y].size() - 1;
            
            for (pair<int, int> pr : cml[y])
                whg[msk[sz1][cnf][pr.first]] = -1;
            
            for (pair<int, int> pr : cml[y]) {
                if (whg[msk[sz1][cnf][pr.first]] == -1)
                    whg[msk[sz1][cnf][pr.first]] = ps++;
                
                arr.push_back(whg[msk[sz1][cnf][pr.first]]);
            }
            
            if (sz2 != -1)
                ps = (int) (lower_bound(msk[sz2].begin(), msk[sz2].end(), arr) - msk[sz2].begin());
            dp[x][cnf] += aux[y][ps];
        }
        
        for (pair<int, int> pr : prl[x])
            if (msk[sz1][cnf][pr.first] == msk[sz1][cnf][pr.second])
                dp[x][cnf] += cst[lst[x][pr.first]][lst[x][pr.second]];
        
        vector<int> arr; int ps = 0;
        int sz2 = (int) cml[x].size() - 1;
        
        for (pair<int, int> pr : cml[x])
            whg[msk[sz1][cnf][pr.second]] = -1;
        
        for (pair<int, int> pr : cml[x]) {
            if (whg[msk[sz1][cnf][pr.second]] == -1)
                whg[msk[sz1][cnf][pr.second]] = ps++;
            
            arr.push_back(whg[msk[sz1][cnf][pr.second]]);
        }
        
        if (sz2 != -1)
            ps = (int) (lower_bound(msk[sz2].begin(), msk[sz2].end(), arr) - msk[sz2].begin());
        aux[x][ps] = min(aux[x][ps], dp[x][cnf]);
    }
    
    return;
}

int main(void) {
    //clock_t bg, en; bg = clock();
    
    int m, n, k;
    in >> m >> n >> k;
    
    for (int i = 0; i + 1 < m; ++i) {
        int x, y;
        in >> x >> y; --x; --y;
        
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    
    for (int i = 0; i < m; ++i) {
        int t;
        in >> t;
        
        lst[i].resize(t);
        for (int &x : lst[i])
            in >> x, --x;
        
        sort(lst[i].begin(), lst[i].end());
        for (int j = 0; j < lst[i].size(); ++j)
            pos[i][lst[i][j]] = j;
    }
    
    int p;
    in >> p;
    
    for (int i = 0; i < p; ++i) {
        int x, y, c;
        in >> x >> y >> c; --x; --y;
        cst[x][y] = cst[y][x] = c;
    }
    
    back(vector<int>(), 0, 0, k);
    dfs(0, -1); out << aux[0][0] << "\n";
    
    //en = clock(); cout << 1.0 * (en - bg) / CLOCKS_PER_SEC;
    return 0;
}