Submission #135710

#	Time	Username	Problem	Language	Result	Execution time	Memory
135710		khsoo01	Political Development (BOI17_politicaldevelopment)	C++11	100 / 100	256 ms	63088 KiB

politicaldevelopment

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 50005, C = 15, B = (1<<10), inf = 1e9;

int n, c, can[C][C], lg[B], ans;
bool chk[N], dt[N][B];

vector<int> adj[N], dir[N], ord;

struct segtree {
	pii v[4*N]; int lim;
	void init () {
		for(lim=1;lim<=n;lim<<=1);
		for(int i=0;i<n;i++) v[lim+i] = pii(adj[i].size(), i);
		for(int i=lim;--i;) v[i] = min(v[2*i], v[2*i+1]);
	}
	void upd (int P, int V) {
		P += lim; v[P].X += V; P >>= 1;
		while(P) {v[P] = min(v[2*P], v[2*P+1]); P >>= 1;}
	}
	pii get (int S, int E) {
		pii R = pii(inf, inf); S += lim; E += lim;
		while(S <= E) {
			if(S%2 == 1) {R = min(R, v[S]); S++;}
			if(E%2 == 0) {R = min(R, v[E]); E--;}
			S >>= 1; E >>= 1;
		}
		return R;
	}
} seg;

int last (int I) {return I&(-I);}

int main()
{
	scanf("%d%d",&n,&c);
	for(int i=0;i<n;i++) {
		int M, T; scanf("%d",&M);
		for(int j=0;j<M;j++) {
			scanf("%d",&T);
			adj[i].push_back(T);
		}
	}
	seg.init();
	for(int i=0;i<n;i++) {
		int I = seg.get(0, n-1).Y;
		for(auto &T : adj[I]) {
			if(!chk[T]) {dir[I].push_back(T); seg.upd(T, -1);}
		}
		seg.upd(I, inf); chk[I] = true;
		ord.push_back(I);
	}
	for(int i=0;i<c;i++) lg[1<<i] = i;
	for(auto &I : ord) {
		for(int i=0;i<dir[I].size();i++) {
			for(int j=0;j<dir[I].size();j++) {
				int A = dir[I][i], B = dir[I][j];
				can[i][j] = false;
				for(auto &T : dir[A]) if(T == B) can[i][j] = true;
			}
		}
		for(int i=1;i<(1<<dir[I].size());i++) {
			int sz = __builtin_popcount(i);
			if(sz == 1) dt[I][i] = true;
			else {
				int B1 = last(i), B2 = last(i-B1);
				if(sz == 2) {
					int A = lg[B1], B = lg[B2];
					dt[I][i] = (can[A][B] || can[B][A]);
				}
				else dt[I][i] = (dt[I][i-B1] && dt[I][i-B2] && dt[I][B1+B2]);
			}
			if(dt[I][i]) ans = max(ans, sz);
		}
	}
	printf("%d\n", ans+1);
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dir[I].size();i++) {
               ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<dir[I].size();j++) {
                ~^~~~~~~~~~~~~~
politicaldevelopment.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&c);
  ~~~~~^~~~~~~~~~~~~~
politicaldevelopment.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int M, T; scanf("%d",&M);
             ~~~~~^~~~~~~~~
politicaldevelopment.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
    ~~~~~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23