Submission #1080451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080451		alexander707070	Road Closures (APIO21_roads)	C++14	0 / 100	2058 ms	24484 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"

#define MAXN 100007
using namespace std;

struct edge{
    int to,flow,cap,rev;
};

int n,a,b,ans[MAXN];
vector<int> v[MAXN];
int parity[MAXN];
vector<edge> g[MAXN];

int ind[MAXN];
vector<int> toupd[MAXN];

void dfs(int x,int p,int dep){
    parity[x]=dep%2;

    for(int i=0;i<v[x].size();i++){
        if(p==v[x][i])continue;
        dfs(v[x][i],x,dep+1);
    }
}

int source,sink,flow,maxflow;

void add_edge(int from,int to,int c){
    g[from].push_back({to,0,c,int(v[to].size())});
    g[to].push_back({to,0,0,int(v[from].size())-1});
}

int vis[MAXN],tim;

int fordfulk(int x,int mins){
    if(x==sink)return mins;

    vis[x]=tim;
    for(int i=0;i<g[x].size();i++){
        if(vis[g[x][i].to]==tim)continue;

        if(g[x][i].flow<g[x][i].cap){
            int curr=fordfulk(g[x][i].to,1);

            if(curr!=0){
                g[x][i].flow++;
                g[g[x][i].to][g[x][i].rev].flow--;
                return 1;
            }
        }
    }

    return 0;
}

void findflow(){
    while(true){
        tim++;

        flow=fordfulk(source,1);
        if(flow==0)break;
        maxflow+=flow;
    }
}

vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
    n=N;

    for(int i=1;i<=n-1;i++){
        a=U[i-1]; b=V[i-1];
        a++; b++;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(1,0,0);

    for(int i=1;i<=n;i++){
        for(int f=2;f<=v[i].size();f++){
            toupd[f].push_back(i);
        }
    }

    source=0; sink=n+1;

    for(int i=1;i<=n;i++){
        if(parity[i]==0){
            add_edge(source,i,1);
            ind[i]=g[source].size()-1;

            for(int f=0;f<v[i].size();f++){
                add_edge(i,v[i][f],1);
            }
        }else{
            add_edge(i,sink,1);
            ind[i]=g[i].size()-1;
        }
    }

    ans[0]=0;
    findflow();
    ans[1]=maxflow;

    for(int i=2;i<=n-1;i++){
        for(int f:toupd[i]){
            if(parity[f]==0){
                g[source][ind[f]].cap++;
            }else{
                g[f][ind[f]].cap++;
            }
        }

        findflow();
        ans[i]=maxflow;
    }

    vector<long long> res;
    for(int i=0;i<=n-1;i++){
        res.push_back(n-1-ans[i]);
    }

    return res;
}

/*int main(){

    vector<long long> s=minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});
    for(long long i:s)cout<<i<<" ";

    return 0;
}*/

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
roads.cpp: In function 'int fordfulk(int, int)':
roads.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int f=2;f<=v[i].size();f++){
      |                     ~^~~~~~~~~~~~~
roads.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int f=0;f<v[i].size();f++){
      |                         ~^~~~~~~~~~~~

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