| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 874090 |
2023-11-16T09:04:46 Z |
simuyu |
Friend (IOI14_friend) |
C++14 |
|
1 ms |
600 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 && p>0) { // RMBR TO REMOVE P>0 LATER
// 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];
}
cout << "HEYYYYYY" << endl;
cout << res0 << ' ' << res1 << endl;
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 {
// check if st5
bool st5 = true;
for (int i=0; i<n; i++) {
if (confidence[i] != 1) {
st5 = false;
break;
}
}
if (st5) {
// st5: bipartite graphs
vector<int> adjlist[n];
for (int guest=1; guest<n; guest++) {
if (protocol[guest] == 0) { // i am your friend
adjlist[host[guest]].push_back(guest);
adjlist[guest].push_back(host[guest]);
} else if (protocol[guest] == 1) { // your friends are my friends
for (int idx=0; idx<(int)adjlist[host[guest]].size(); idx++) {
int person = adjlist[host[guest]][idx];
adjlist[person].push_back(guest);
adjlist[guest].push_back(person);
}
}
}
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];
}
//cout << "HEYYYYYY" << endl;
//cout << res0 << ' ' << res1 << endl;
return max(res0, res1);
} else {
// do whole graph with all. st1 or st5 (or unsolved st6)
return 0; // TODO
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 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 |
1 ms |
348 KB |
Output is correct |
| # |
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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
444 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
600 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
600 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
