1218 - Perfect Service

brianfry713 · Post by **brianfry713** » Sat May 25, 2013 2:12 am

Input:

AC output: 392

Farsan · Post by **Farsan** » Fri Oct 03, 2014 11:43 am

WA and the only testcase given by brianfry is too big to debug.

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const


using namespace std;

int dp[10002][2];
vector<int>g[10002],v[10002];
bool visited[10002];

int dfs(int no)
{
    visited[no]=true;
    int i,j,k;
    for(i=0,j=v[no].size();i<j;i++)
    {
        k=v[no][i];
        if(!visited[k])
        {
            g[no].push_back(k);
            //g[k].push_back(no);
            dfs(k);
        }
    }
}

int solve(int no,int place,int root)
{

    if(dp[no][place]!=-1)
    return dp[no][place];
    int i,j,k,m,n,a,b,c,d,mx;
    if(root)
    {
        if(place)
        {
            k=0;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,0,0);
                b=solve(m,1,0);
                c=min(a,b);
                k=k+c;
            }
            return dp[no][place]=1+k;
        }
        else
        {
            mx=inf;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,1,0);
                for(b=0,j=g[no].size();b<j&&a!=inf;b++)
                {
                    n=g[no][b];
                    if(m==n)
                    continue;
                    a=a+solve(n,0,0);
                }
                mx=min(mx,a);
            }
            return dp[no][place]=mx;
        }
    }
    else
    {
        if(place)
        {
            k=0;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,0,0);
                b=solve(m,1,0);
                c=min(a,b);
                k=k+c;
            }
            return dp[no][place]=1+k;
        }
        else
        {
            mx=inf;
            for(i=0,j=g[no].size();i<j;i++)
            {
                m=g[no][i];
                a=solve(m,1,0);
                for(b=0,j=g[no].size();b<j&&a!=inf;b++)
                {
                    n=g[no][b];
                    if(n==m)
                    continue;
                    a=a+solve(n,0,0);
                }
                mx=min(mx,a);
            }
            if(j==0)
            mx=0;
            return dp[no][place]=mx;
        }
    }
}


int main()
{
    int i,j,k,m,n,a,b;
    while(inp1(n))
    {
        for(i=1;i<=n;i++)
        {
            v[i].clear();
            g[i].clear();
            dp[i][0]=-1;
            dp[i][1]=-1;
            visited[i]=false;
        }
        for(i=1;i<n;i++)
        {
            inp2(j,k);
            v[j].push_back(k);
            v[k].push_back(j);
        }
        for(i=1,j=0;i<=n;i++)
        {
            if(!visited[i])
            {
                dfs(i);
                a=solve(i,0,1);
                b=solve(i,1,1);
                j=j+min(a,b);
            }
        }
        cout<<j<<endl;
        inp1(k);
        if(k==-1)
        break;
    }
    return 0;
}

brianfry713 · Post by **brianfry713** » Sat Oct 04, 2014 1:02 am

Input:

Code: Select all

AC output:

Code: Select all

OJ Board

1218 - Perfect Service

1218 - Perfect Service

Re: 1218 - Perfect Service

Re: 1218 - Perfect Service