Submission #1017390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017390		Ice_man	Friend (IOI14_friend)	C++14	23 / 100	1 ms	2908 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];


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[])
{
    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:149:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int i = to[node]; i < v[node].size(); i++ , to[node]++)
      |                               ~~^~~~~~~~~~~~~~~~

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