Submission #561460

#	Time	Username	Problem	Language	Result	Execution time	Memory
561460		fatemetmhr	Friends (BOI17_friends)	C++17	100 / 100	163 ms	6736 KiB

friends

//  ~Be name khoda~  //
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  25e2  + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;
 
int grsz, mxed, pos = 0;
vector <int> verex, adj[maxn5], av[maxn5], tmp, esh;
int grsize, outedge, haveout[maxn5];
bool re, ntm[maxn5], ex[maxn5];
bool ex1[maxn5], ex2[maxn5];
bool ed[maxn5][maxn5], ab[maxn5];
int nn, exex[maxn5];
 
inline void kill(){
    cout << "detention" << endl;
    exit(0);
}
 
inline void solve(){
    if(grsize > grsz || outedge > mxed)
        return;
    if(re)
        return;
    int v = -1;
    for(auto u : verex) for(auto z : adj[u]) if(ntm[z]){
        v = z;
    }
    if(v == -1){
        av[pos] = verex;
        re = true;
        return;
    }
 
    ntm[v] = false;
    ex[v] = true;
    verex.pb(v);
    grsize++;
    int remem = outedge;
    for(auto u : adj[v]) if(!ntm[u] && !ex[u])
        outedge++;
    solve();
    if(re)
        return;
    verex.pop_back();
    ex[v] = false;
    grsize--;
    outedge = remem;
    for(auto u : adj[v]) if(!ntm[u] && ex[u])
        outedge++;
    solve();
    if(re)
        return;
    outedge = remem;
    ntm[v] = true;
    return;
}

inline void update(int id){
    for(auto u : av[id])
        ex[u] = true;
    haveout[id] = 0;
    for(auto u : av[id]) for(auto z : adj[u])
        haveout[id] += (!ex[z]);
    for(auto u : av[id])
        ex[u] = false;

}
 
inline void mostaghel_kon(int id1, int id2){
    if(av[id1].empty() || av[id2].empty())
        return;
    esh.clear();
    for(auto u : av[id1])
        ex1[u] = true;
    for(auto u : av[id2])
        ex2[u] = true;
    for(auto u : av[id2]) if(ex1[u]){
        esh.pb(u);
        ab[u] = true;
    }
    if(esh.empty()){
        for(auto u : av[id1])
            ex1[u] = false;
        for(auto u : av[id2])
            ex2[u] = false;
        for(auto u : esh)
            ab[u] = false;
        return;
    }

    int ext1 = 0, ext2 = 0;
    for(auto u : esh) for(auto z : adj[u]) if(!ab[z]){
        if(ex1[z])
            ext1++;
        if(ex2[z])
            ext2++;
    }
    tmp.clear();
    int rpid = id1;
    if(ext1 + haveout[id1] - ext2 <= mxed){
        for(auto u : av[id1]) if(!ab[u])
            tmp.pb(u);
        haveout[id1] += ext1;
    }
    else{
        rpid = id2;
        for(auto u : av[id2]) if(!ab[u])
            tmp.pb(u);
        haveout[id2] += ext2;
    }
    for(auto u : av[id1])
        ex1[u] = false;
    for(auto u : av[id2])
        ex2[u] = false;
    for(auto u : esh)
        ab[u] = false;
    av[rpid] = tmp;
    update(id1);
    update(id2);
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
    int n; cin >> n >> grsz >> mxed;
    nn = n;
 
    for(int i = 0; i < n; i++){
        int l; cin >> l;
        while(l--){
            int a; cin >> a;
            ed[i][a] = true;
            adj[i].pb(a);
        }
    }
    for(int i = 0; i < n; i++) if(adj[i].size() > grsz + mxed)
        kill();
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
        if(ed[i][j] != ed[j][i])
            kill();
 
    for(int i = 0; i < n; i++){
        memset(ntm, true, sizeof ntm);
        ex[i] = true;
        ntm[i] = re = false;
        outedge = 0;
        grsize = 1;
        verex.clear();
        verex.pb(i);
        solve();
        if(!re)
            kill();
        haveout[pos] = outedge;
        pos++;
    }
    memset(ex, false, sizeof ex);
    memset(ex1, false, sizeof ex1);
    memset(ex2, false, sizeof ex2);
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
        mostaghel_kon(i, j);
    int cnt = 0;
    for(int i = 0; i < n; i++)
        cnt += (av[i].size() > 0);

    cout << "home" << endl;
    cout << cnt << endl;
    for(int i = 0; i < n; i++) if(av[i].size()){
        cout << av[i].size() << ' ';
        for(auto u : av[i])
            cout << u << ' ';
        cout << '\n';
    }
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:154:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  154 |     for(int i = 0; i < n; i++) if(adj[i].size() > grsz + mxed)
      |                                   ~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 37 / 37
• Subtask 3: 12 / 12
• Subtask 4: 31 / 31