oj.uz

Submission #30971

# Submission time Handle Problem Language Result Execution time Memory
30971 2017-08-02T05:14:33 Z kajebiii Friend (IOI14_friend) C++14
100 / 100
 49 ms 8472 KB 
#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 1e5 + 100;

int N, Nr[MAX_N], Cnt[3];
vector<int> Ed[MAX_N];
void makeG(int ho[], int pr[]) {
    for(int i=1; i<N; i++) {
        int h = ho[i];
        if(pr[i] >= 1) for(int x : Ed[h]) Ed[x].push_back(i), Ed[i].push_back(x);
        if(pr[i] % 2 == 0) Ed[h].push_back(i), Ed[i].push_back(h);
    }
}
int Dy[MAX_N][2]; bool Vis[MAX_N];
void getDy(int v, int p) {
    Vis[v] = true;
    Dy[v][1] = Nr[v];
    for(int w : Ed[v]) if(w != p) {
        getDy(w, v);
        Dy[v][0] += max(Dy[w][0], Dy[w][1]);
        Dy[v][1] += Dy[w][0];
    }
}

int Color[MAX_N];
void Coloring(int v, int p, int c) {
    Vis[v] = true;
    Color[v] = c;
    for(int w : Ed[v]) if(Vis[w] == false) Coloring(w, v, 1-c);
}

bool bVis[MAX_N]; int Match[MAX_N];
bool findMatch(int v) {
    if(bVis[v]) return false; bVis[v] = true;
    for(int w : Ed[v]) if(Color[w] == 1) if(Match[w] == -1 || findMatch(Match[w])) {
        Match[w] = v;
        return true;
    }
    return false;
}

int sDy[MAX_N][2]; // 0 : use or not use , 1 : not use
int solve(int ho[], int pr[]) {
    for(int i=0; i<N; i++) sDy[i][0] = Nr[i];
    for(int i=N-1; i>=1; i--) {
        int h = ho[i], p = pr[i];
        if(p == 0) {
            sDy[h][0] += sDy[i][1];
            sDy[h][1] += sDy[i][0];
        }else if(p == 1) {
            sDy[h][0] += sDy[i][0];
            sDy[h][1] += sDy[i][1];
        }else if(p == 2) {
            sDy[h][0] = max(sDy[h][0] + sDy[i][1], sDy[h][1] + sDy[i][0]);
            sDy[h][1] += sDy[i][1];
        }
        sDy[h][0] = max(sDy[h][0], sDy[h][1]);
    }
    return sDy[0][0];
}
int findSample(int n_, int nr_[], int ho_[], int pr_[]) {
    N = n_; for(int i=0; i<N; i++) Nr[i] = nr_[i];
    
    for(int i=1; i<N; i++) Cnt[pr_[i]]++;

    if(N <= 10) {
        int d[15][15] = {0, };
        makeG(ho_, pr_);
        for(int v=0; v<N; v++) for(int w : Ed[v]) d[v][w] = 1;
        int ans = 0;
        for(int s=0; s<(1<<N); s++) {
            vector<int> list;
            for(int i=0; i<N; i++) if(s & (1<<i)) list.push_back(i);
            bool isCan = true;
            for(int x : list) for(int y : list) if(d[x][y] == 1) {isCan = false; break;}
            if(isCan) {
                int sum = 0;
                for(int x : list) sum += Nr[x];
                ans = max(ans, sum);
            }
        }
        return ans;
    }

    if(Cnt[2] == N-1) {
        int maxV = -1;
        for(int i=0; i<N; i++) maxV = max(maxV, Nr[i]);
        return maxV;
    }else if(Cnt[1] == N-1) {
        int sum = 0;
        for(int i=0; i<N; i++) sum += Nr[i];
        return sum;
    }else if(Cnt[0] == N-1) {
        makeG(ho_, pr_);
        int sum = 0;
        for(int i=0; i<N; i++) if(Vis[i] == false) {
            getDy(i, -1);
            sum += max(Dy[i][0], Dy[i][1]);
        }
        return sum;
    }

    bool AllOne = true;
    for(int i=0; i<N; i++) if(Nr[i] != 1) {AllOne = false; break;}
    if(AllOne && (Cnt[1] + Cnt[0]) == N-1) {
        makeG(ho_, pr_);
        for(int i=0; i<N; i++) if(Vis[i] == false) Coloring(i, -1, 0);
        for(int i=0; i<N; i++) Match[i] = -1;

        int flow = 0;
        for(int i=0; i<N; i++) if(Color[i] == 0) {
            for(int j=0; j<N; j++) bVis[j] = false;
            flow += findMatch(i);
        }
        return N - flow;
    }

    
    return solve(ho_, pr_);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8472 KB Output is correct
6 Correct 0 ms 8472 KB Output is correct
7 Correct 0 ms 8472 KB Output is correct
8 Correct 0 ms 8472 KB Output is correct
9 Correct 0 ms 8472 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct
11 Correct 0 ms 8472 KB Output is correct
12 Correct 0 ms 8472 KB Output is correct
13 Correct 0 ms 8472 KB Output is correct
14 Correct 0 ms 8472 KB Output is correct
15 Correct 0 ms 8472 KB Output is correct
16 Correct 3 ms 8472 KB Output is correct
17 Correct 0 ms 8472 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 3 ms 8472 KB Output is correct
5 Correct 3 ms 8472 KB Output is correct
6 Correct 0 ms 8472 KB Output is correct
7 Correct 0 ms 8472 KB Output is correct
8 Correct 0 ms 8472 KB Output is correct
9 Correct 0 ms 8472 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8472 KB Output is correct
6 Correct 0 ms 8472 KB Output is correct
7 Correct 0 ms 8472 KB Output is correct
8 Correct 0 ms 8472 KB Output is correct
9 Correct 0 ms 8472 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8472 KB Output is correct
6 Correct 0 ms 8472 KB Output is correct
7 Correct 0 ms 8472 KB Output is correct
8 Correct 3 ms 8472 KB Output is correct
9 Correct 0 ms 8472 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct
11 Correct 0 ms 8472 KB Output is correct
12 Correct 0 ms 8472 KB Output is correct
13 Correct 3 ms 8472 KB Output is correct
14 Correct 0 ms 8472 KB Output is correct
15 Correct 0 ms 8472 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8472 KB Output is correct
6 Correct 0 ms 8472 KB Output is correct
7 Correct 0 ms 8472 KB Output is correct
8 Correct 0 ms 8472 KB Output is correct
9 Correct 0 ms 8472 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct
11 Correct 0 ms 8472 KB Output is correct
12 Correct 0 ms 8472 KB Output is correct
13 Correct 0 ms 8472 KB Output is correct
14 Correct 0 ms 8472 KB Output is correct
15 Correct 0 ms 8472 KB Output is correct
16 Correct 0 ms 8472 KB Output is correct
17 Correct 0 ms 8472 KB Output is correct
18 Correct 0 ms 8472 KB Output is correct
19 Correct 3 ms 8472 KB Output is correct
20 Correct 0 ms 8472 KB Output is correct
21 Correct 3 ms 8472 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8472 KB Output is correct
6 Correct 0 ms 8472 KB Output is correct
7 Correct 0 ms 8472 KB Output is correct
8 Correct 0 ms 8472 KB Output is correct
9 Correct 0 ms 8472 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct
11 Correct 0 ms 8472 KB Output is correct
12 Correct 39 ms 8472 KB Output is correct
13 Correct 16 ms 8472 KB Output is correct
14 Correct 33 ms 8472 KB Output is correct
15 Correct 49 ms 8472 KB Output is correct