Cod sursa(job #979029)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 31 iulie 2013 10:24:44
Problema Tproc Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.58 kb
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int VMAX = 4200;
const int NMAX = 512;
const int KMAX = 8;
const int INF = 0x3f3f3f3f;
 
#define FORI(p, X) for (typeof((X).begin()) p = (X).begin(); p != (X).end(); ++p)
#define PB push_back
 
int N, M, K, P, NP;
int INC[NMAX][NMAX], SAT[NMAX];
vector <int> G[NMAX], T[NMAX], PERM[VMAX];
int used[KMAX], D[NMAX][VMAX], BUF[NMAX][VMAX];
int jump[KMAX][KMAX][VMAX];
 
void read(void) {
    ifstream fin("tproc.in");
    int i, j, u, v, c, cnt;
 
    fin >> M >> N >> K;
 
    for (i = 1; i < M; ++i) {
        fin >> u >> v;
        G[u].PB(v); G[v].PB(u);
    }
 
    for (i = 1; i <= M; ++i) {
        fin >> cnt;
        T[i].resize(cnt);
        for (j = 0; j < cnt; ++j)
            fin >> T[i][j];
    }
 
    fin >> P;
 
    for (i = 0; i < P; ++i) {
        fin >> u >> v >> c;
        INC[u][v] = INC[v][u] = c;
    }
 
    fin.close();
}
 
void DFS(int k, int t) {   
    FORI(p, G[k])
        if (*p != t)
            DFS(*p, k);
     
    if (t) {
        int d = 0;
        FORI(p, T[k]) {
            FORI(q, T[t])
                if (*p == *q) {
                    swap(*p, T[k][d++]);
                    break;
                }
        }
        SAT[k] = d;
    }
}
 
void back(vector <int> V, int k) {
    if ((int) V.size() == KMAX) {
        PERM[NP++] = V;
    } else {
        int i;
 
        V.PB(0);
        for (i = 0; i <= k && i < K; ++i)
            *V.rbegin() = i,
            back(V, max(k, i+1));
    }
}
 
int solve(int, int, int);
 
inline void complete(int k, int v, int &ans, int pos, int call, int tata) {
    int i;
 
    if (k == (int) T[call].size()) {
        ans = min(ans, solve(call, pos, tata));
    } else {
        for (i = 0; i <= v && i < K; ++i)
            complete(k+1, max(v, i+1), ans, jump[k][i][pos], call, tata);
    }
}
 
int solve(int gr, int op, int tata) {
    if (D[gr][op] != -1)
        return D[gr][op];
 
    int i, j, u, cost = 0;
 
    for (i = 0; i < (int) T[gr].size(); ++i)
        for (j = max(i+1, SAT[gr]); j < (int) T[gr].size(); ++j)
            if (PERM[op][i] == PERM[op][j])
                cost += INC[ T[gr][i] ][ T[gr][j] ];
 
    FORI(p, G[gr]) {
        if (*p == tata) continue;
             
        memset(used, 0xff, sizeof(used));
        int cnt = 0, ans = INF, pos = 0, v;
 
        for (i = 0; i < SAT[*p]; ++i) {
            for (j = 0; T[gr][j] != T[*p][i]; ++j);
            u = PERM[op][j];
            v = ( (used[u] == -1 ? (used[u] = cnt++) : used[u]) );
            pos = jump[i][v][pos];
        }
         
        if (BUF[*p][pos] == -1) {
            complete(SAT[*p], cnt, ans, pos, *p, gr);
            BUF[*p][pos] = ans;
        }
        cost += BUF[*p][pos];
    }
 
    return D[gr][op] = cost;
}
 
void write(void) {
    ofstream fout("tproc.out");
 
    fout << D[0][0] << '\n';
 
    fout.close();
}
 
void prep(vector <int> V, int p, int k) {
    if ((int) V.size() == KMAX) return;
    int i, q;
 
    V.PB(0);
    for (i = 0; i <= k && i < K; ++i) {
        *V.rbegin() = i;
     
        q = lower_bound(PERM + p, PERM + NP, V) - PERM;
 
        jump[V.size() - 1][i][p] = q;
         
        prep(V, q, max(k, i+1));
    }
 
}
 
int main(void) {
 
    read();
 
    DFS(1, 0);
 
    back(vector <int> (), 0);
 
    prep(vector <int> (), 0, 0);
 
    memset(D, 0xff, sizeof(D));
    memset(BUF, 0xff, sizeof(BUF));
    G[0].PB(1);
    solve(0, 0, 0);
 
    write();
 
    return 0;
}