Friday, 19 December 2014

INOI Sequence Land solution

#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
int main(){
    int n=scan();
    int k=scan();
    vector<int> a[301];//which person has ith id
    vector<int> arr[301];//ids the ith person has
    for(int i=1;i<=n;i++){
        int id=scan();
        while(id--){
            int x=scan();
            arr[i].push_back(x);//ith person has the id (x)
            a[x].push_back(i);//x id is with ith person
        }
    }//makin the graph O(n^3)
    vector<int> v[301];
    for(int i=1;i<=n;i++){//ith person
        int temp[301]={0};//number of ids common between the ith person and others
        int x=arr[i].size();
        for(int j=0;j<x;j++){
            int id = arr[i][j];
            int y=a[id].size();
            for(int l=0;l<y;l++){
                int person = a[id][l];
                temp[person]++;
                if(temp[person]>=k){
                    v[i].push_back(person);
                }
            }
        }
    }
    //bfs;
    queue<int> q;
    bool visited[301]={0};
    int ans=0;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(!visited[u]){
            ans++;
        }
        visited[u]=1;
        int x=v[u].size();
        for(int i=0;i<x;i++){
            int node = v[u][i];
            if(!visited[node]){
                q.push(node);
            }
        }
    }
    cout<<ans;
}

1 comment:

  1. Sorry Runtime Error. Its bug finding time I will inform you if I find the bug

    ReplyDelete