oj.uz

Submission #521359

# Submission time Handle Problem Language Result Execution time Memory
521359 2022-02-01T23:46:30 Z Yazan_Alattar Friends (BOI17_friends) C++14
20 / 100
 1 ms 844 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 2507;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void close(){ cout << "detention" << endl; exit(0); }

vector <int> adj[M], group[M];
int n, P, Q, in[M];
bool vist[M], frnd[M][M];

bool valid(vector <int> v)
{
    int q = 0;
    for(auto i : v) vist[i] = 1;
    for(auto i : v) for(auto j : adj[i]) if(!vist[j]) ++q;
    for(auto i : v) vist[i] = 0;
    return (v.size() <= P && q <= Q);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> P >> Q;
    for(int i = 1; i <= n; ++i){
        int m;
        cin >> m;
        for(int j = 1; j <= m; ++j){
            int x;
            cin >> x; ++x;
            adj[i].pb(x);
            frnd[i][x] = 1;
        }
        if(m > P + Q) close();
    }
    for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= n; ++j) if(frnd[i][j] != frnd[j][i]) close();
    for(int i = 1; i <= n; ++i){
        for(int mask = 0; mask < (1 << adj[i].size()); ++mask){
            vector <int> v;
            v.pb(i);
            for(int j = 0; j < adj[i].size(); ++j) if((mask >> j) & 1) v.pb(adj[i][j]);
            if(valid(v)){
                group[i] = v;
                break;
            }
        }
        if(group[i].empty()) close();
    }
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            vector <int> xi, xj, yi, yj;
            for(auto k : group[i]) in[k] |= 1;
            for(auto k : group[j]) in[k] |= 2;
            for(auto k : group[i]){
                if(in[k] == 1){
                    xi.pb(k);
                    xj.pb(k);
                }
                else yj.pb(k);
            }
            for(auto k : group[j]){
                if(in[k] == 2){
                    yi.pb(k);
                    yj.pb(k);
                }
                else xi.pb(k);
            }
            if(valid(xi) && valid(yi)){
                group[i] = xi;
                group[j] = yi;
            }
            else{
                group[i] = xj;
                group[j] = yj;
            }
            for(auto k : group[i]) in[k] = 0;
            for(auto k : group[j]) in[k] = 0;
        }
    }
    cout << "home\n";
    vector < vector <int> > ans;
    for(int i = 1; i <= n; ++i) if(group[i].size()){
        vector <int> v;
        for(auto j : group[i]) v.pb(j);
        ans.pb(v);
    }
    cout << ans.size() << endl;
    for(auto i : ans){
        cout << i.size() << " ";
        for(auto j : i) cout << j - 1 << " ";
        cout << endl;
    }
    return 0;
}

Compilation message

friends.cpp: In function 'bool valid(std::vector<int>)':
friends.cpp:39:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     return (v.size() <= P && q <= Q);
      |             ~~~~~~~~~^~~~
friends.cpp: In function 'int main()':
friends.cpp:62:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int j = 0; j < adj[i].size(); ++j) if((mask >> j) & 1) v.pb(adj[i][j]);
      |                            ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 37.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Incorrect 1 ms 844 KB Output isn't correct
11 Halted 0 ms 0 KB -