oj.uz

Submission #58974

# Submission time Handle Problem Language Result Execution time Memory
58974 2018-07-19T23:09:10 Z FLDutchman Friend (IOI14_friend) C++14
100 / 100
 64 ms 8024 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1100;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

/*
vi match;
bitset<NMAX> vis;
vi adj[NMAX];

int aug(int n){
    if(vis[n]) return 0;
    vis[n] = 1;
    for(int k : adj[n]) if(match[k] == -1 || aug(match[k])) {
        match[k] = n;
        match[n] = k;
        return 1;
    }
    return 0;
}

int MCBM(){
    int tot = 0;
    FOR(i, 0, NMAX) if(match[i] == -1) vis.reset(), tot += aug(i);
    return tot;
}


INT findSample(INT n, INT confidence[], INT host[], INT protocol[]){
    FOR(i, 1, n){
        if(protocol[i] == 0 || protocol[i] == 2){
            adj[host[i]].pb(i);
            adj[i].pb(host[i]);
            //cout << i << " " << host[i] << endl;
        }
        if(protocol[i] == 1 || protocol[i] == 2){
            for(int k : adj[host[i]]){
                //cout << i << " " << k << endl;
                adj[k].pb(i);
                adj[i].pb(k);
            }
        }
    }
    match.assign(NMAX, -1);
    //cout<<endl;
    int m = MCBM();
    FOR(i, 0, n){
        cout << i << " " << match[i] << endl;
    }
    return n - m;
}
*/

INT findSample(INT n, INT confidence[], INT host[], INT protocol[]){
    vii c;
    FOR(i, 0, n) c.pb({confidence[i], 0});
    for(int i = n-1; i > 0; i--) {
        //cout<<i<<endl;
        int h = host[i], p = protocol[i];
        int p1 = c[h].fst, q1 = c[h].snd,
            p2 = c[i].fst, q2 = c[i].snd;
        if(p == 0) c[h] = { p1 + q2, max(p2 + q1, q2 + q1) };
        if(p == 1) c[h] = { max(max(p1 + p2, p1 + q2), p2 + q1), q1 + q2 };
        if(p == 2) c[h] = { max(p1 + q2, p2 + q1), q1 + q2 };
    }
    //<<c[0].fst<<endl;
    return max(c[0].fst, c[0].snd);
}
/*
signed main(){
    fast_io();
    int N;
    INT conf[NMAX], host[NMAX], protocol[NMAX];
    cin >> N;
    FOR(i, 0, N) cin >> conf[i];
    FOR(i, 1, N) cin >> host[i], cin >> protocol[i];
    cout << findSample(N, conf, host, protocol) << endl;
    
}


6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0



*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 3 ms 652 KB Output is correct
17 Correct 2 ms 652 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

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

Subtask #5
23.0 / 23.0

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

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 964 KB Output is correct
2 Correct 3 ms 964 KB Output is correct
3 Correct 3 ms 964 KB Output is correct
4 Correct 3 ms 964 KB Output is correct
5 Correct 2 ms 964 KB Output is correct
6 Correct 3 ms 964 KB Output is correct
7 Correct 3 ms 992 KB Output is correct
8 Correct 3 ms 996 KB Output is correct
9 Correct 3 ms 996 KB Output is correct
10 Correct 3 ms 996 KB Output is correct
11 Correct 2 ms 996 KB Output is correct
12 Correct 64 ms 5632 KB Output is correct
13 Correct 29 ms 5632 KB Output is correct
14 Correct 52 ms 7060 KB Output is correct
15 Correct 60 ms 8024 KB Output is correct