Submission #1269845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269845		Jakub_Wozniak	Training (IOI07_training)	C++20	0 / 100	31 ms	8520 KiB

training

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const int oo = (1e+9)+9;
const int base = (1<<19);
const int maxn = 7*(1e+3)+9;
const int mod = 998244353;
struct sc
{
    int a , b;
    int c;
};
int S = 0;
int N  ,M ;
vector <int> t[maxn];
vector <int> s[maxn];
vector <int> addi[maxn];
vector <sc> V;
vector <sc> Vreal; // chwilowe
ll sum = 0;
int dep[maxn];
int ktuo[maxn];
int dp[maxn][1 << 10];
int lca[maxn]; //lca dla danej pary o indeksie i
vector<pii> podddsc[maxn]; // poddrzewa dla danej sciezki o indeksie i , {poddrzewo , ktore sciezkie usuiete}
int mskall[maxn]; //maska gdy wszyscy synowie sa ok
vector <int> sclca[maxn]; // sciezkie ktorych lca to i
int sumsc[maxn]; // suma wartosci dp poddrzew sciezki poza lca
int PC[maxn]; // ktore sciezki z lca sa zajete przez dana sciezke

void DFSdep(int v, int o)
{
    dep[v] = dep[o]+1;
    for(auto p : t[v])
    {
        if(p == o)continue;;
        ktuo[p] = s[v].size();
        s[v].push_back(p);
        DFSdep(p,v);
    }

    for(auto p : addi[v])
    {
        if(V[p].b == v)continue;

        if(abs(dep[v] - dep[V[p].b])%2)
        {
            sum += V[p].c;
        }
        else
        {
            Vreal.push_back(V[p]);
        }
    }
}


int asc = -1 , bsc = -1  , aktind = -1;
int DFSsc(int v)
{
    int sumloc = 0;
    if(v == asc)sumloc++;
    if(v == bsc)sumloc++;
    int a1 = -1 , a2 = -1;
    mskall[v] = (1<< (s[v].size()))-1;
    for(auto p : s[v])
    {
        int temp = DFSsc(p);
        if(temp)
        {
            if(a1 == -1)a1 = p;
            else a2 = p;
        }
        sumloc += temp;
    }

    if(a1 != -1)
    {
        if(a2 == -1)podddsc[aktind].push_back({v , mskall[v]^(1 << ktuo[a1])});
        else podddsc[aktind].push_back({v , mskall[v]^(1 << ktuo[a1])^(1 << ktuo[a2])});
    }

    if(sumloc == 2)
    {
        lca[aktind] = v;
        if(a2 != -1)PC[aktind] = (1 << ktuo[a1])^(1 << ktuo[a2]);
        else PC[aktind] = (1 << ktuo[a1]);
        sumloc = 0;
    }
    return sumloc;
}

void scpre()
{
    for(int i = 0; i < V.size() ; i++)
    {
        asc = V[i].a;
        bsc = V[i].b;
        aktind = i;
        DFSsc(S);
        sclca[lca[i]].push_back(i);
    }
}

void DFS(int v)
{
    int sumloc = 0;
    for(auto p : s[v])
    {
        DFS(p);
        sumloc += dp[p][mskall[p]];
    }
    for(auto i : sclca[v])
    {
        for(auto p : podddsc[i])
        {
            if(p.st != v)sumsc[i] += dp[p.st][p.nd];
        }
    }

    dp[v][0] = 0;
    for(int j = 1; j <= mskall[v] ; j++)
    {
        sumloc = 0;
        for(int i = 0; i < s[v].size() ; i++)
        {
            if((j&(1<<i)))sumloc += dp[s[v][i]][mskall[s[v][i]]];
        }
        dp[v][j] = sumloc;

        for(auto i : sclca[v])
        {
            if((j&PC[i]) != PC[i])continue;
            dp[v][j] = max(dp[v][j] , sumsc[i] + dp[v][(j^PC[i])] + V[i].c);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int a , b , c;
    for(int i = 0 ;i < M ; i++)
    {
        cin >> a >> b >> c;
        if(c == 0)
        {
            t[a].push_back(b);
            t[b].push_back(a);
        }
        else
        {
            sc temp;
            temp.a = a;
            temp.b = b;
            temp.c = c;
            addi[a].push_back(V.size());
            addi[b].push_back(V.size());
            V.push_back(temp);
        }
    }

    for(int i = 1 ; i <= N ; i++)
    {
        if(t[i].size() == 1)S = i;
    }

    dep[0] = 0;
    DFSdep(S,0);
    V = Vreal;
    scpre();

    for(int i =0 ; i < V.size() ; i++)
    {
        auto p = V[i];
    }

    for(auto p : V)sum += p.c; 
    DFS(S);
    cout << sum-dp[S][mskall[S]] << '\n';
    


    
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9