oj.uz

답안 #183932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
183932 2020-01-10T08:21:27 Z Ruxandra985 Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 13 ms 4600 KB 
#include <bits/stdc++.h>
#define DIMN 50010
using namespace std;
map <int,int> mp[DIMN];
vector <int> v[DIMN];
int grad[DIMN] , f[DIMN] , l[DIMN];
pair <int,int> dp[DIMN];
priority_queue <pair <int,int> > h;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , k , i, elem , nod , vecin , x , ok , ok2 , i2 , j , sol , val , conf;
    fscanf (fin,"%d%d",&n,&k);
    for (i=0;i<n;i++){
        fscanf (fin,"%d",&elem);
        for (j=1;j<=elem;j++){
            fscanf (fin,"%d",&x);
            mp[i][x] = 1;
            v[i].push_back(x);
        }
        grad[i] = elem;
        h.push(make_pair(-grad[i] , i));
    }
    sol = 0;
    while (!h.empty()){
        nod = h.top().second;
        val = -h.top().first;
        h.pop();
        if (grad[nod] != val)
            continue;
        f[nod] = 1;
        /// ok acum avem nodul cu cel mai mic grad
        /// vrei sa vezi daca poate apartine unui graf complet
        elem = 0;
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            if (!f[vecin]) /// nu are rost sa faci heapul mai mare decat e nevoie
                l[++elem] = vecin;
        }

        /// din graful complet curent face parte nod si un subset din l
        ok = 0;
        dp[++ok] = make_pair(0 , 1); /// doar nod

        for (i = 1 ; i <= elem ; i++){

            ok2 = ok;
            for (j = 1 ; j <= ok2 ; j ++){
                /// adaugi l[i] la configuratia dp[j].first
                x = l[i];
                conf = dp[j].first;
                for (i2 = 0 ; i2 <= k ; i2++){
                    if ( (conf & (1 << i2)) && !mp[x][l[i2+1]] )
                        break;
                }
                if (i2 > k){
                    dp[++ok] = make_pair(conf + (1 << (i-1)) , dp[j].second + 1);
                    sol = max(sol , dp[j].second + 1);
                }
            }

        }

        /// il eliminam
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            grad[vecin]--;
            if (!f[vecin]) /// nu are rost sa faci heapul mai mare decat e nevoie
                h.push(make_pair(-grad[vecin] , vecin));
        }
    }
    fprintf (fout,"%d",sol);
    return 0;
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:14:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:16:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&elem);
         ~~~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:18:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&x);
             ~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3832 KB Output is correct
2 Correct 5 ms 3832 KB Output is correct
3 Correct 11 ms 4600 KB Output is correct
4 Correct 8 ms 4600 KB Output is correct
5 Correct 10 ms 4600 KB Output is correct
6 Correct 13 ms 4600 KB Output is correct
7 Correct 5 ms 4600 KB Output is correct
8 Incorrect 6 ms 3960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3832 KB Output is correct
2 Correct 5 ms 3832 KB Output is correct
3 Correct 11 ms 4600 KB Output is correct
4 Correct 8 ms 4600 KB Output is correct
5 Correct 10 ms 4600 KB Output is correct
6 Correct 13 ms 4600 KB Output is correct
7 Correct 5 ms 4600 KB Output is correct
8 Incorrect 6 ms 3960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3832 KB Output is correct
2 Correct 5 ms 3832 KB Output is correct
3 Correct 11 ms 4600 KB Output is correct
4 Correct 8 ms 4600 KB Output is correct
5 Correct 10 ms 4600 KB Output is correct
6 Correct 13 ms 4600 KB Output is correct
7 Correct 5 ms 4600 KB Output is correct
8 Incorrect 6 ms 3960 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3832 KB Output is correct
2 Correct 5 ms 3832 KB Output is correct
3 Correct 11 ms 4600 KB Output is correct
4 Correct 8 ms 4600 KB Output is correct
5 Correct 10 ms 4600 KB Output is correct
6 Correct 13 ms 4600 KB Output is correct
7 Correct 5 ms 4600 KB Output is correct
8 Incorrect 6 ms 3960 KB Output isn't correct
9 Halted 0 ms 0 KB -