Submission #726355

#	Time	Username	Problem	Language	Result	Execution time	Memory
726355		n0sk1ll	Road Closures (APIO21_roads)	C++17	12 / 100	56 ms	13068 KiB

roads

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#include "roads.h"

graph g(100005);
int deg[100005];
bool marked[100005];
int kolko=0;

vector<li> solve_brute(int n, vector<int> u, vector<int> v, vector<int> w)
{

}

vector<li> solve_star(int n, vector<int> w)
{
    li tsum=0;
    sort(all(w));
    for (auto it : w) tsum+=it;

    vector<li> ans;
    ans.pb(tsum);
    while (!w.empty())
    {
        tsum-=w.back();
        w.popb();
        ans.pb(tsum);
    }

    return ans;
}

li dp[100005];
vector<li> solve_line(int n, vector<int> w) //podsetnik: w ima duzinu n-1
{
    vector<li> ans;
    ans.pb(0);
    for (auto it : w) ans.back()+=it;

    if (n==2)
    {
        ans.pb(w[0]);
        return ans;
    }

    dp[0]=w[0];
    dp[1]=w[1];

    ff(i,2,n-1) dp[i]=w[i]+min(dp[i-2],dp[i-1]);
    ans.pb(min(dp[n-3],dp[n-2]));
    while ((int)ans.size()<n) ans.pb(0ll);
    return ans;
}

vector<int> koji[100005];

vector<li> solve_without_weights(int n, vector<int> u, vector<int> v)
{
    ff(i,0,n-1) deg[u[i]]++,deg[v[i]]++;
    ff(i,0,n) koji[deg[i]].pb(i);

    ff(i,0,n-1) g[u[i]].pb(v[i]);
    ff(i,0,n-1) g[v[i]].pb(u[i]);

    int sirov=0,spas=0;
    vector<li> ans;
    bff(i,0,n)
    {
        sirov+=kolko; ans.pb(sirov-spas);
        for (auto p : koji[i])
        {
            kolko++;
            marked[p]=true;
            for (auto it : g[p]) if (marked[it]) spas++;
        }
    }

    reverse(all(ans));
    return ans;
}

vector<li> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w)
{
    bool is_star=true;
    ff(i,0,n-1) if (u[i]!=0) is_star=false;
    if (is_star) return solve_star(n,w);

    bool is_line=true;
    ff(i,0,n-1) if (u[i]!=i || v[i]!=i+1) is_line=false;
    if (is_line) return solve_line(n,w);

    bool weightless=true;
    ff(i,0,n-1) if (w[i]>1) weightless=false;
    if (weightless) return solve_without_weights(n,u,v);

    return solve_brute(n,u,v,w);
}

/*

5
0 1 1
0 2 1
1 3 1
1 4 1

*/

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> solve_brute(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:47:1: warning: no return statement in function returning non-void [-Wreturn-type]
   47 | }
      | ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22