Submission #1269797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269797		Jakub_Wozniak	Training (IOI07_training)	C++20	30 / 100	2 ms	584 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 = (1e+3)+9;
const int mod = 998244353;
struct sc
{
    int a , b;
    int c;
};
int N  ,M ;
vector <int> t[maxn];
vector <int> addi[maxn];
vector <sc> V;
vector <sc> Vreal;
ll sum = 0;
int dep[maxn];

vector <int> kol; //sciezka
ll dp[maxn]; //sciezka
int kt[maxn] ; // sciezka



void DFSdep(int v, int o)
{
    kol.push_back(v);
    dep[v] = dep[o]+1;
    for(auto p : t[v])
    {
        if(p == o)continue;;
        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 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);
        }
    }

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

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



    for(int i = 1; i <= N ; i++)addi[i].clear();

    for(int i = 0; i < V.size() ; i++)
    {
        if(dep[V[i].a] > dep[V[i].b])swap(V[i].a , V[i].b);
        addi[V[i].b].push_back(i);
        sum += V[i].c;
    }

    for(int i = 0; i < kol.size() ; i++)
    {
        kt[kol[i]] = i;
    }

    dp[0] = 0;
    for(int i = 1; i < kol.size() ; i++)
    {
        dp[i] = dp[i-1];
        for(auto p : addi[kol[i]])
        {
            dp[i] = max(dp[i] , (dp[kt[V[p].a]] + V[p].c));
        }
    }

    cout << sum - dp[N-1] << '\n';


    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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