Submission #240009

#	Time	Username	Problem	Language	Result	Execution time	Memory
240009		nicolaalexandra	Wiring (IOI17_wiring)	C++14	0 / 100	11 ms	9728 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define DIM 200010
#define INF 2000000000000000000LL
using namespace std;

set <pair<int,long long> > L[DIM];
long long dp[DIM][2];
int f[DIM],Left0[DIM],Left1[DIM],Right0[DIM],Right1[DIM];
pair <int,int> v[DIM];

int modul (int n){
    return max (n,-n);
}

void add_edge (int x, int y, long long cost){
    L[x].insert(make_pair(y,cost));
    L[y].insert(make_pair(x,cost));
    //cout<<x<<" "<<y<<" "<<cost<<endl;
}

void dfs (int nod, int tata){

    int ok = 0;
    for (auto it : L[nod]){
        int vecin = it.first;
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
        }}

    if (!ok){
        f[nod] = 1;
        dp[nod][1] = INF;
    } else {

        /// dp[nod][0/1] - costul minim daca il am pe nod cuplat sau nu
        /// daca nod e legat de o frunza nu pot sa am dp[nod][0]
        int ok = 0;
        for (auto it : L[nod]){
            int vecin = it.first;
            if (vecin == tata)
                continue;

            if (f[vecin]){
                ok = 1;
                break;
            }}

        if (ok){
            dp[nod][0] = INF;
            for (auto it : L[nod]){
                int vecin = it.first, cost = it.second;
                if (vecin == tata)
                    continue;
                dp[nod][1] += min (dp[vecin][1], dp[vecin][0] + cost);
            }

        } else {
            /// pot sa calculez ambele stari

            for (auto it : L[nod]){
                int vecin = it.first, cost = it.second;
                if (vecin == tata)
                    continue;
                dp[nod][0] += dp[vecin][1];
            }

            /// dp[nod][1] -> trb sa ma asigur ca va fi legat macar de un fiu!!
            int ap = 0;
            for (auto it : L[nod]){
                int vecin = it.first, cost = it.second;
                if (vecin == tata)
                    continue;
                if (dp[vecin][0] + cost <= dp[vecin][1]){
                    dp[nod][1] += dp[vecin][0] + cost;
                    ap = 1;
                } else dp[nod][1] += dp[vecin][1];
            }

            if (!ap){
                long long mini = INF;
                for (auto it : L[nod]){
                    int vecin = it.first, cost = it.second;
                    if (vecin == tata)
                        continue;
                    mini = min (mini,dp[nod][1] - dp[vecin][1] + dp[vecin][0] + cost);
                }
                dp[nod][1] = mini;
            }}}}

long long min_total_length(vector<int> r, vector<int> b) {
    int k = 0, i;
    for (auto it : r)
        v[++k] = make_pair(it,0);
    for (auto it : b)
        v[++k] = make_pair(it,1);

    sort (v+1,v+k+1);

    for (i=1;i<=k;i++){
        if (v[i].second == 0){
            Left0[i] = i;
            Left1[i] = Left1[i-1];
        } else {
            Left0[i] = Left0[i-1];
            Left1[i] = i;
        }
    }

    for (i=k;i;i--){
        if (v[i].second == 0){
            Right0[i] = i;
            Right1[i] = Right1[i+1];
        } else {
            Right0[i] = Right0[i+1];
            Right1[i] = i;
        }
    }

    for (i=1;i<=k;i++){

        if (v[i].second == 0){
            long long dist_left = INF, dist_right = INF;
            if (Left1[i])
                dist_left = modul (v[i].first - v[Left1[i]].first);
            if (Right1[i])
                dist_right = modul (v[i].first - v[Right1[i]].first);

            if (dist_left <= dist_right)
                add_edge (i,Left1[i],dist_left);
            if (dist_right <= dist_left)
                add_edge (i,Right1[i],dist_right);

        } else {
            long long dist_left = INF, dist_right = INF;
            if (Left0[i])
                dist_left = modul (v[i].first - v[Left0[i]].first);
            if (Right0[i])
                dist_right = modul (v[i].first - v[Right0[i]].first);

            if (dist_left <= dist_right)
                add_edge (i,Left0[i],dist_left);
            if (dist_right <= dist_left)
                add_edge (i,Right0[i],dist_right);
        }

    }

    dfs (1,0);

    return dp[1][1];

}

Compilation message (stderr)

wiring.cpp: In function 'void dfs(int, int)':
wiring.cpp:63:39: warning: unused variable 'cost' [-Wunused-variable]
                 int vecin = it.first, cost = it.second;
                                       ^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45