Submission #1017734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017734		Ice_man	Friend (IOI14_friend)	C++14	69 / 100	24 ms	5980 KiB

friend

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <queue>

#include "friend.h"

#define maxn 1005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


vector <int> v[maxn];
bool nb[maxn][maxn];

void add(int a, int b)
{
    v[a].pb(b);
    v[b].pb(a);

    nb[a][b] = true;
    nb[b][a] = true;
}


int dp[maxn][2];
int c[maxn];

bool used[maxn];

void dfs(int node, int par)
{
    used[node] = true;
    dp[node][1] = c[node];

    for(int& e : v[node])
    {
        if(e == par)
            continue;

        dfs(e, node);

        dp[node][1] += dp[e][0];
        dp[node][0] += max(dp[e][0], dp[e][1]);
    }
}


struct max_flow
{
    struct edge
    {
        int from, to;
        int c, flow;

        edge() {};

        edge(int _from, int _to, int _c, int _flow = 0)
        {
            from = _from;
            to = _to;
            c = _c;
            flow = _flow;
        }
    };

    int n;
    vector <vector <int>> v;
    vector <int> used, to;
    vector <edge> e;

    void init(int _n)
    {
        n = _n;
        e.clear();
        used.resize(n + 1);
        v.resize(n + 1);
        to.resize(n + 1);
    }

    int bre;

    void add_edge(int from, int to, int c)
    {
        v[from].pb(bre);
        v[to].pb(bre + 1);

        e.push_back({from, to, c});
        e.push_back({to, from, 0});

        bre += 2;
    }

    queue <int> q;

    bool bfs(int start, int endd)
    {
        for(int i = 0; i <= n; i++)
            used[i] = -1;
        used[start] = 0;

        q.push(start);

        int node;
        while(q.size() != 0)
        {
            node = q.front();
            q.pop();

            for(int idx : v[node])
                if(used[e[idx].to] == -1 && e[idx].c > e[idx].flow)
                {
                    q.push(e[idx].to);
                    used[e[idx].to] = used[node] + 1;
                }
        }

        return used[endd] == -1? false : true;
    }

    int fix_flow(int node, int endd, int fl)
    {
        if(node == endd || fl == 0)
            return fl;

        int idx, nb;

        for(int i = to[node]; i < v[node].size(); i++, to[node]++)
        {
            idx = v[node][i];
            nb = e[idx].to;

            if(used[nb] != used[node] + 1)
                continue;

            if(e[idx].c <= e[idx].flow)
                continue;

            int fix = fix_flow(nb, endd, min(fl, e[idx].c - e[idx].flow));
            if(fix == 0)
                continue;

            e[idx].flow += fix;
            e[idx ^ 1].flow -= fix;

            return fix;
        }
        return 0;
    }

    int find_flow(int start, int endd)
    {
        int ans = 0;

        while(bfs(start, endd) == true)
        {
            for(int i = 0; i <= n; i++)
                to[i] = 0;

            int curr;
            while((curr = fix_flow(start, endd, INF)))
                ans += curr;
        }

        return ans;
    }

};


int type[maxn];

void bfs(int start)
{
    type[start] = 1;

    queue <int> q;
    q.push(start);

    while(q.size() != 0)
    {
        int node = q.front();
        q.pop();

        for(int& e : v[node])
        {
            if(type[e] != 0)
                continue;

            if(type[node] == 1)
                type[e] = 2;
            else
                type[e] = 1;
            q.push(e);
        }
    }
}




int findSample(int n, int confidence[], int host[], int protocol[])
{

    for(int i = 0; i < n; i++)
        c[i] = confidence[i];

    if(n <= 10)
    {
        for(int i = 1; i < n; i++)
            if(protocol[i] == 0)
                add(host[i], i);
            else if(protocol[i] == 1)
                for(int& e : v[host[i]])
                    add(e, i);
            else
            {
                for(int& e : v[host[i]])
                    add(e, i);
                add(host[i], i);
            }

        int maxx = -INF;
        for(int mask = 0; mask < (1 << n); mask++)
        {
            int sum = 0;
            for(int i = 0; i < n; i++)
                if((mask & (1 << i)) > 0)
                    sum += confidence[i];

            int pom = 1;
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    if((mask & (1 << i)) > 0 && (mask & (1 << j)) > 0)
                        if(nb[i][j] == true)
                            pom = 0;
            if(pom == 0)
                continue;

            maxx = max(maxx, sum);
        }

        return maxx;
    }

    bool gr2 = true;
    bool gr3 = true;
    bool gr4 = true;

    for(int i = 1; i < n; i++)
        if(protocol[i] == 0)
            gr2 = false, gr3 = false;
        else if(protocol[i] == 1)
            gr3 = false, gr4 = false;
        else
            gr4 = false, gr2 = false;

    if(gr3 == true)
        return *max_element(confidence, confidence + n);

    if(gr2 == true)
    {
        int sum = 0;

        for(int i = 0; i < n; i++)
            sum += c[i];

        return sum;
    }

    if(gr4 == true)
    {
        for(int i = 1; i < n; i++)
            if(protocol[i] == 0)
                add(host[i], i);
            else if(protocol[i] == 1)
                for(int& e : v[host[i]])
                    add(e, i);
            else
            {
                for(int& e : v[host[i]])
                    add(e, i);
                add(host[i], i);
            }

        int ans = 0;

        for(int node = 0; node < n; node++)
            if(used[node] == false)
            {
                dfs(node, n + 1);
                ans += max(dp[node][0], dp[node][1]);
            }
        return ans;
    }


    max_flow G;

    for(int i = 0; i < n; i++)
        c[i] = confidence[i];

    for(int i = 1; i < n; i++)
        if(protocol[i] == 0)
            add(host[i], i);
        else if(protocol[i] == 1)
            for(int& e : v[host[i]])
                add(e, i);
        else
        {
            for(int& e : v[host[i]])
                add(e, i);
            add(host[i], i);
        }

    for(int node = 0; node < n; node++)
        if(type[node] == 0)
            bfs(node);
    G.init(n + 3);

    for(int i = 0; i < n; i++)
        if(type[i] == 2)
            G.add_edge(i, n + 1, 1);
        else
        {
            for(int& e : v[i])
                G.add_edge(i, e, 1);
            G.add_edge(n, i, 1);
        }

    return n - G.find_flow(n, n + 1);
}
















/**int main()
{

#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    add(1 , 1 , 10 , 2 , 9 , 4);
    _remove(1 , 1 , 10 , 5 , 10 , 1);
    _remove(1 , 1 , 10 , 4 , 7 , 5);
    add(1 , 1 , 10 , 1 , 6 , 3);
    add(1 , 1 , 10 , 3 , 3 , 5);
    _remove(1 , 1 , 10 , 7 , 8 , 0);

    answer(1 , 1 , 10);
    for(int i = 0; i < 10; i++)
        cout << ans[i] << " ";
    cout << endl;



    return 0;
}
*/

Compilation message (stderr)

friend.cpp: In member function 'int max_flow::fix_flow(int, int, int)':
friend.cpp:166:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         for(int i = to[node]; i < v[node].size(); i++, to[node]++)
      |                               ~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31