Submission #1120158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120158		RSAMSD	Bosses (BOI16_bosses)	C++17	100 / 100	580 ms	848 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
int t = 0;
int const f = 5e3 + 10;
long long mod = 1e9 + 7;//998244353;
long long dp1[f][5];
long long dp2[f];
long long par[f];
long long a[f];
long long mmn =0;
pair<long long, long long> edges[f];
long long prefix[f];
vector<long long>g[f];
vector<pair<int,int>>gg[f];
struct node {
	long long val = 0;
	long long lazy = 0;
};
struct trpel {
	long long v, u, bank = 0;
};
node segtree[f * 8];
bool B[f];
void redany() {
	ifstream fin;
	ofstream fout;
	fin.open("std.in");
	fout.open("std.out");
}
void build(int v , int l , int r){
	if(r==l){
		segtree[v].val = 1e9;
		return;
	}
	int mid = (r+l)/2;
	build(2*v+1,mid+1,r);
	build(2*v,l,mid);
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
void upd(int v, int l, int r , int pos, int val){
	if(r==l&&r==pos){
		segtree[v].val = val;
		return;
	}
	int mid = (r+l)/2;
	if(pos>mid){
		upd(2*v+1,mid+1,r,pos,val);
	}
	else{
		upd(2*v,l,mid,pos,val);
	}
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
long long q(int v, int tl , int tr , int l ,int r){
	if(tl>r||tr<l)return 0;
	if(tr<=r&&tl>=l){
		return segtree[v].val;
	}
	int mid = (tr+tl)/2;
	return max(q(2*v,tl,mid,l,r),q(2*v+1,mid+1,tr,l,r));
}
// void merge(int a , int b, int n, int id){
	// if(g[a].size()>g[b].size()){
		// swap(a,b);
	// }
	// for(int u:g[a]){
		// if(u<n&&!B[u]&&par[u+1]==b){
			// upd(1,1,n,u,id);
			// B[u]=1;
		// }
		// if(u>1&&!B[u-1]&&par[u-1]==b){
			// upd(1,1,n,u-1,id);
			// B[u-1] =1;
		// }
		// g[b].push_back(u);
		// par[u] = b;
	// }
// }
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
long long tw = powmod(2, mod - 2, mod);
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	//cin >> t;
	t = 1;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		string s3;
		char s2;
		long double dec = 0;
		bool c = 1;
		priority_queue<pair<long long, long long>> qq;
		multiset<long long> mul;
		queue<long long> pp;
		map<pair<long long, pair<long long, long long>>, long long> conv;
		vector<long long> vec;
		cin >> n;
		for(int i =1;i<=n;i++){
			cin>>d;
			for(int j =0;j<d;j++){
				cin>>r;
				g[r].push_back(i);
			}
		}
		mx = 1e18;
		for(int i =1;i<=n;i++){
			fill(dp2,dp2+n+1,0);
			fill(B,B+n+1,0);
			dp2[i] = 1;
			pp.push(i);
			d=0;
			B[i] = 1;
			while(!pp.empty()){
				k = pp.front();
				pp.pop();
				d+=dp2[k];
				for(int u:g[k]){
					if(!B[u]){
						pp.push(u);
						dp2[u] = dp2[k]+1;
						B[u] =1;
					}
				}
			}
			for(int i =1;i<=n;i++){
				if(!B[i]){
					d = 1e18;
					break;
				}
			}
			mx = min(mx,d);
			
		}
		cout<<mx;
	}
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:103:31: warning: unused variable 'm' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                               ^
bosses.cpp:103:45: warning: unused variable 'k2' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                             ^~
bosses.cpp:103:60: warning: unused variable 'rr' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                            ^~
bosses.cpp:103:68: warning: unused variable 'l' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                    ^
bosses.cpp:103:75: warning: unused variable 'll' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                           ^~
bosses.cpp:103:83: warning: unused variable 'lll' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                   ^~~
bosses.cpp:103:92: warning: unused variable 'rrr' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                            ^~~
bosses.cpp:103:101: warning: unused variable 'inf' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                                     ^~~
bosses.cpp:106:8: warning: unused variable 's2' [-Wunused-variable]
  106 |   char s2;
      |        ^~
bosses.cpp:107:15: warning: unused variable 'dec' [-Wunused-variable]
  107 |   long double dec = 0;
      |               ^~~
bosses.cpp:108:8: warning: unused variable 'c' [-Wunused-variable]
  108 |   bool c = 1;
      |        ^

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33