oj.uz

Submission #421000

# Submission time Handle Problem Language Result Execution time Memory
421000 2021-06-08T16:08:13 Z marcipan5000 Friend (IOI14_friend) C++14
69 / 100
 41 ms 4344 KB 
#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

bool q1=1,q2=1,q3=1;
int n1;
int ans=0;
int uu;



int conff[1002];
vector<int> t[1002];
bool z[15];
int w=0;
void rek(int p) {
    if (p==n1) {
        for (int i=0;i<n1;i++) {
            if (z[i]==1) {
                for (int j=0;j<t[i].size();j++) {
                    if (z[t[i][j]]==1) {
                        return;
                    }
                }
            }
        }
        ans=max(ans,w);
        return;
    }
    z[p]=0;
    rek(p+1);
    z[p]=1; w+=conff[p];
    rek(p+1);
    z[p]=0; w-=conff[p];
    return;
}

const int maxn = (int)1e3;

vector<bool> volt;
vector<int> par;
bool javit(int akt, bool p){
    volt[akt] = true;
    if(par[akt] != -1 && p)
        return javit(par[akt], !p);
    for(int x : t[akt]){
        if(!volt[x] && (par[x] == -1 || javit(x, !p))){
            par[akt] = x;
            par[x] = akt;
            return true;
        }
    }
    return false;
}

int subtask5(int n){
    par.assign(n, -1);
    int maxmatching = 0;
    for(int i = 0; i < n; i++){
        volt.assign(n, false);
        if(par[i] == -1 && javit(i, false))
            maxmatching++;
    }
    return n-maxmatching;
}

bool vo[1002];
pair<int,int> z2;
pair<int,int> dfs(int p) {
    vo[p]=1;
    pair<int,int> ans;
    ans.first=0;
    ans.second=0;
    for (int i=0;i<t[p].size();i++) {
        if (vo[t[p][i]]==0) {
            z2=dfs(t[p][i]);
            ans.second+=max(z2.first,z2.second);
            ans.first+=z2.second;
        }
    }
    ans.first+=conff[p];
    return(ans);
}

int findSample(int n,int confidence[],int host[],int protocol[]) {
    n1=n;
    for (int i=1;i<n;i++) {
        if (protocol[i]!=0) {
            q1=0;
        }
        if (protocol[i]!=1) {
            q2=0;
        }
        if (protocol[i]!=2) {
            q3=0;
        }
    }
    for (int i=0;i<n;i++) {
        conff[i]=confidence[i];
    }
    for (int i=1;i<n;i++) {
            if (protocol[i]==0) {
               t[i].push_back(host[i]);
               t[host[i]].push_back(i);
            }
            if (protocol[i]==1) {
                uu=t[host[i]].size();
                for (int j=0;j<uu;j++) {
                    t[i].push_back(t[host[i]][j]);
                    t[t[host[i]][j]].push_back(i);
                }
            }
            if (protocol[i]==2) {
                uu=t[host[i]].size();
                for (int j=0;j<uu;j++) {
                    t[i].push_back(t[host[i]][j]);
                    t[t[host[i]][j]].push_back(i);
                }
                t[i].push_back(host[i]);
                t[host[i]].push_back(i);
            }
    }
    if (q3==1) {
        int ma=0;
        for (int i=0;i<n;i++) {
            ma=max(ma,confidence[i]);
        }
        return(ma);
    }
    if (q2==1) {
        int ma=0;
        for (int i=0;i<n;i++) {
            ma=ma+confidence[i];
        }
        return(ma);
    }
    if (q1==1) {
        z2=dfs(0);
        return(max(z2.first,z2.second));
    }


    if (n<=10) {


            /*
            for (int i2=0;i2<=i;i2++) {
                for (int j=0;j<t[i2].size();j++) {
                    cout << t[i2][j] << " ";
                }
                    cout << endl;
                }
            cout << endl;
            */


        rek(0);
        return(ans);
    }
    return(subtask5(n));
}

Compilation message

friend.cpp: In function 'void rek(int)':
friend.cpp:21:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                 for (int j=0;j<t[i].size();j++) {
      |                              ~^~~~~~~~~~~~
friend.cpp: In function 'std::pair<int, int> dfs(int)':
friend.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i=0;i<t[p].size();i++) {
      |                  ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1228 KB Output is correct
2 Correct 12 ms 4196 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 7 ms 3020 KB Output is correct
5 Correct 12 ms 4044 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 14 ms 4344 KB Output is correct

Subtask #4
19.0 / 19.0

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

Subtask #5
23.0 / 23.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Runtime error 41 ms 2740 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -