oj.uz

Submission #874049

# Submission time Handle Problem Language Result Execution time Memory
874049 2023-11-16T08:30:41 Z simuyu Friend (IOI14_friend) C++14
16 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
#define f first
#define s second

int findSample(int n, int confidence[], int host[], int protocol[]) {
    int p = protocol[1];
    bool st234 = true;
    for (int idx=2; idx<n; idx++) {
        if (protocol[idx] != p) {
            st234=false;
            break;
        }
    }

    if (st234) {
        // subtasks 2, 3, 4
        if (p==0) { // IAmYourFriend, st4

            /*
            // just get all pairs by host and host index
            int res = 0;
            for (int guest=1; guest<n; guest++) {
                res = max(res, confidence[host[guest]] + confidence[guest] );
            }
            return res;
            */

            // THIS FORMS A TREE!!

            // prep for bfs to bipartite graph
            vector<int> adjlist[n];
            for (int guest=1; guest<n; guest++) {
                adjlist[host[guest]].push_back(guest);
                adjlist[guest].push_back(host[guest]);
            }

            int types[n];
            for (int i=0; i<n; i++) types[i] = -1;
            // bfs
            queue<pair<int, int> > q;
            q.push(pair<int,int>(0,0));

            pair<int,int> data;
            while (!q.empty()) {
                data = q.front(); q.pop();
                if (types[data.f] != -1) continue; // if go back to parent
                types[data.f] = data.s;
                for (int idx=0; idx<(int)adjlist[data.f].size(); idx++) {
                    q.push(pair<int,int>( adjlist[data.f][idx] , 1-data.s ) ); // push neighbours to other colour
                }
            }

            int res0=0, res1=0;
            for (int i=0; i<n; i++) {
                if (types[i] == 0) res0 += confidence[i];
                else res1 += confidence[i];
            }

            return max(res0, res1);

        } else if (p==2) { // MyFriendsAreYourFriends, st3
            // nobody is freinds lol, just get max
            int res = 0;
            for (int person=0; person<n; person++) {
                res = max(res, confidence[person]);
            }
            return res;

        } else if (p==1) { // WeAreYourFriends, st2
            // it's just all of them summed up
            int res = 0;
            for (int person=0; person<n; person++) {
                res += confidence[person];
            }
            return res;

        } else {
            // smtg weird
            return -1;

        }
    } else {
        // do whole graph with all. st1 or st5 (or unsolved st6)
        return 0; // TODO
    }

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -