Submission #7317

#	Time	Username	Problem	Language	Result	Execution time	Memory
7317		myungwoo	Friend (IOI14_friend)	C++98	53 / 100	32 ms	7296 KiB

friend

#include <queue>
#include <vector>
using namespace std;
 
#define MAXN 100005
#define pb push_back
#define sz(v) ((int)(v).size())
 
static int N,*A,*H,*P;
static vector<int> con[MAXN];
static bool visit[MAXN];
 
void connect(int a,int b){ con[a].pb(b); con[b].pb(a); }
 
void drawGraph()
{
    int i,j;
    for (i=1;i<N;i++){
        switch (P[i]){
        case 0: connect(H[i],i); break;
        case 1:
            for (j=sz(con[H[i]]);j--;) connect(con[H[i]][j],i);
            break;
        case 2:
            for (j=sz(con[H[i]]);j--;) connect(con[H[i]][j],i);
            connect(H[i],i);
            break;
        }
    }
}
 
int dfs(int n,int val)
{
    int i,k,ret=0;
    if (n == N) return val;
    for (i=sz(con[n]);i--;){
        k = con[n][i];
        if (visit[k]) break;
    }
    if (i < 0){
        visit[n] = 1;
        ret = dfs(n+1,val+A[n]);
    }
    visit[n] = 0;
    int v = dfs(n+1,val);
    if (ret < v) ret = v;
    return ret;
}
 
int subtask1()
{
    drawGraph();
    return dfs(0,0);
}
 
int subtask2()
{
    int ret=0,i;
    for (i=0;i<N;i++) ret += A[i];
    return ret;
}
 
int subtask3()
{
    int ret=0,i;
    for (i=0;i<N;i++) if (ret < A[i]) ret = A[i];
    return ret;
}
 
static int par[MAXN],D[MAXN][2];
 
void dy(int n)
{
    int i,k;
    D[n][1] = A[n];
    for (i=sz(con[n]);i--;){
        k = con[n][i];
        if (par[n] == k) continue;
        par[k] = n; dy(k);
        D[n][0] += D[k][1]; D[n][1] += D[k][0];
    }
    if (D[n][1] < D[n][0]) D[n][1] = D[n][0];
}
 
int subtask4()
{
    drawGraph(); dy(0);
    return D[0][1];
}
 
static int color[MAXN],match[MAXN],dist[MAXN];
static bool used[MAXN];
 
void coloring(int n,int c)
{
    int i,k;
    color[n] = c;
    for (i=sz(con[n]);i--;){
        k = con[n][i];
        if (!color[k]) coloring(k,3-c);
    }
}
 
void bfs()
{
    int i;
    queue <int> que;
    for (i=0;i<N;i++) dist[i] = 1e9;
    for (i=0;i<N;i++) if (color[i] == 1 && !used[i]) dist[i] = 0, que.push(i);
    while (!que.empty()){
        int q = que.front(); que.pop();
        for (i=sz(con[q]);i--;){
            int k = con[q][i], m = match[k];
            if (m >= 0 && dist[m] == 1e9) dist[m] = dist[q]+1, que.push(m);
        }
    }
}
 
bool hck(int n)
{
    int i;
    for (i=sz(con[n]);i--;){
        int k = con[n][i], m = match[k];
        if (m == -1 || dist[m] == dist[n]+1 && hck(m)){
            used[n] = 1; match[k] = n;
            return 1;
        }
    }
    return 0;
}
 
int subtask5()
{
    int ret=N,i;
    drawGraph();
    for (i=0;i<N;i++) if (!color[i]) coloring(i,1);
    for (i=0;i<N;i++) match[i] = -1;
    for (int flow=1;flow;){
        bfs();
        flow = 0;
        for (i=0;i<N;i++) if (color[i] == 1 && !used[i] && hck(i)) flow++;
        ret -= flow;
    }
    return ret;
}
 
int findSample(int n,int confidence[],int host[],int protocol[])
{
    int i;
    N = n; A = confidence; H = host; P = protocol;
    if (N <= 10) return subtask1();
    for (i=1;i<N;i++) if (protocol[i-1] != protocol[i]) break;
    if (i == N){
        switch (protocol[0]){
        case 0: return subtask4();
        case 1: return subtask2();
        case 2: return subtask3();
        }
    }
    for (i=1;i<N;i++) if (protocol[i] == 2) break;
    if (i == N && N <= 1000){
        for (i=0;i<N;i++) if (A[i] != 1) break;
        if (i == N) return subtask5();
    }
    return 0;
}

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