oj.uz

답안 #238475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238475 2020-06-11T13:47:59 Z nicolaalexandra 친구 (IOI14_friend) C++14
35 / 100
 9 ms 5248 KB 
#include <bits/stdc++.h>
#include "friend.h"
#define DIM 100010
using namespace std;

set <int> L[DIM];
int dp[DIM][2],t[DIM],sum[DIM],viz[DIM];
vector <pair<int,int> > mch;

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

void _union (int x, int y){
    int radx = get_rad(x), rady = get_rad(y);
    if (radx == rady)
        return;
    if (t[radx] > t[rady])
        swap (radx,rady);

    t[radx] += t[rady];
    t[rady] = radx;
    sum[radx] += sum[rady];
}

void dfs (int nod, int tata){

    viz[nod] = 1;
    for (auto vecin : L[nod]){
        if (vecin != tata)
            dfs (vecin,nod);
    }

    dp[nod][1] = sum[nod];
    for (auto vecin : L[nod]){
        if (vecin != tata){
            dp[nod][0] += max(dp[vecin][0],dp[vecin][1]);
            dp[nod][1] += dp[vecin][0];
        }}}

int findSample (int n, int confidence[], int host[], int tip[]){
    int i, nr0 = 0, nr1 = 0, nr2 = 0;
    for (i=1;i<n;i++){
        if (tip[i] == 0)
            nr0++;
        if (tip[i] == 1)
            nr1++;
        if (tip[i] == 2)
            nr2++;
    }
    if (nr1 == n-1){ /// nu am nicio muchie

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

        return sol;
    }

    if (nr2 == n-1){ /// graf complet
        int sol = 0;
        for (i=0;i<n;i++)
            sol = max (sol,confidence[i]);
        return sol;
    }


    if (nr2 == 0){

        for (i=1;i<=n;i++){
            t[i] = -1;
            sum[i] = confidence[i-1];
        }

        for (i=1;i<n;i++){
            int x = host[i] + 1, y = i+1;

            if (tip[i] == 0) /// i am your friend
                mch.push_back(make_pair(x,y));
            else _union (x,y);

        }

        /// acum trb sa unesc toate multimele astea si se formeaza mai multi arbori

        for (auto it : mch){
            int x = it.first, y = it.second;
            int radx = get_rad(x), rady = get_rad(y);
            if (radx != rady){
                L[radx].insert(rady);
                L[rady].insert(radx);
            }
        }

        int sol = 0;

        for (i=1;i<=n;i++){
            if (!viz[i]){
                dfs (i,0);
                sol += max (dp[i][0],dp[i][1]);
            }}

        return sol;

    }
	/// acum devine mai complicat:)))
}

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 9 ms 4992 KB Output is correct
7 Incorrect 7 ms 4992 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 8 ms 4992 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 8 ms 4992 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 9 ms 4992 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 8 ms 5120 KB Output is correct
13 Correct 9 ms 5248 KB Output is correct
14 Correct 9 ms 5120 KB Output is correct
15 Correct 8 ms 5120 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Incorrect 7 ms 5120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Incorrect 8 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -