?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
90598516 |
Contestant: roshan_mehta |
1401D - 33 | C++17 (GCC 9-64) | Wrong answer on pretest 5 | 77 ms | 15924 KB | 2020-08-21 18:54:33 | 2020-08-21 18:54:33 |
// "It does not matter how slowly you go as long as you do not stop." - Confucius #include <bits/stdc++.h> using namespace std; /* author : Roshan_Mehta motto : Time Management,Consistency,Patience!! */ #define int long long #ifdef Local_Debug #define debug(x) cout<<#x <<" "<<x<<" " #define debug1(a) cout <<#a<<" " <<a << endl #define debug2(a, b) cout <<#a<<" "<< a << " "<<#b<<" " << b << endl #define debug3(a, b, c) cout <<#a<<" "<<a << " "<<#b<<" " << b << " "<<#c<<" " << c << endl #define debug4(a, b, c, d) cout << #a<<" "<<a << " " <<#b<<" "<< b << " "<<#c<<" " << c << " "<<#d<<" "<< d << endl void show(vector<int> &a) {for (int i = 0; i < a.size(); i++) {cout << a[i] << " ";}cout << endl;} void show(vector<vector<int>> &a) { for(int i=0;i<a.size();i++) { for(int j=0;j<a[i].size();j++) { cout<<a[i][j]<<" "; } cout<<endl; } } void show(vector<pair<int,int>> &a) { for (int i = 0; i < (int)a.size(); i++) { cout<<a[i].first<<" "<<a[i].second<<endl; } } void printTime(clock_t begin) { printf("%.3lf seconds\n", (double) (clock() - begin) / CLOCKS_PER_SEC); } #else #define debug(x) #define debug1(x) #define debug2(x,y) #define debug3(x,y,z) #define debug4(x,y,z,a) void show(vector<int> &a){return;} void show(vector<vector<int>> &a){return;} void show(vector<pair<int,int>> &a){return ;} void printTime() {return;} #endif #define M1 1000000007 #define M2 998244353 #define G(a,b) get<a>(b) #define ll long long #define pb push_back #define mt make_tuple #define fast() ios_base::sync_with_stdio(false);cin.tie(NULL); #define mp make_pair #define F first #define S second #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rsort(x) sort(x,greater<int> ()) #define rall(x) rbegin(x), rend(x) //useful in sorting #define endl "\n" #define p0(a) cout << a << " " #define p1(a) cout << a << endl #define p2(a, b) cout << a << " " << b << endl #define p3(a, b, c) cout << a << " " << b << " " << c << endl #define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl #define gcd __gcd #define deci(n) fixed << setprecision(n) #define test() int test_case;cin >> test_case;while (test_case--) #define loop(i,a,n) for(int i=a;i<n;i++) #define sp " " #define popcount(x) __builtin_popcount(x) #define popcountll(x) __builtin_popcountll(x) #define clz(x) __builtin_clz(x) #define clzll(x) __builtin_clzll(x) #define ctz(x) __builtin_ctz(x) #define ctzll(x) __builtin_ctzll(x) #define max3(a,b,c) max(max(a,b),c) #define min3(a,b,c) min(min(a,b),c) #define max4(a,b,c,d) max(a,max3(b,c,d)) #define min4(a,b,c,d) min(a,min3(b,c,d)) #define max5(a,b,c,d,e) max(max4(a,b,c,d),e) #define min5(a,b,c,d,e) min(min4(a,b,c,d),e) #define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());} #define REP(i,a,b) for(ll i=a;i<b;i++) #define REPI(i,a,b) for(ll i=b-1;i>=a;i--) typedef vector<int> vi; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<ll> vl; typedef vector<vi> vvi; typedef pair<int, int> pi; typedef vector<pi> vpi; typedef pair<int,pi> tri; typedef pair<pi,int> rtri; typedef pair<ll, ll> pl; typedef pair<double, double> pd; typedef priority_queue<int, vector<int>, greater<int>> minpq; typedef priority_queue<int> pq; typedef unordered_map<int,int> umii; typedef map<int,int> mii; typedef set<int> si; #define input(n,k) int n,k;cin>>n;cin>>k;vi arr(n,0);loop(i,0,n){cin>>arr[i];} const int MOD = 1e9 + 7; int md=MOD; int Power(int n, int x) {int ans = 1;while (x > 0) {if (x & 1) ans = (ans * n) % md; n = (n * n) % md;x = x >> 1;}return ans;} vl fact, inv; void inverse(ll n) {if(n>=inv.size()){ll size=inv.size();size=size==0? 1:size; inv.resize(n + 1);inv[0] = 1; for (ll i = size; i <= n; i++)inv[i] = Power(fact[i], md - 2);}} void factorial(ll n) {if(n>=fact.size()){ll size=fact.size();size=size==0? 1:size; fact.resize(n + 1);fact[0] = 1;for (ll i = size; i <= n; i++) fact[i] = (fact[i - 1] * i) % md; }} ll ncr(ll n, ll r) { return (((fact[n] * inv[r]) % md) * inv[n - r]) % md; } vl SieveOfEratosthenes(int n) { bool prime[n+1]; memset(prime, true, sizeof(prime)); for (int p=2; p*p<=n; p++) {if (prime[p] == true){for (int i=p*p; i<=n; i += p) prime[i] = false;}} vl ans;for (int p=2; p<=n; p++)if (prime[p])ans.pb(p);return ans; } vi primeFactors(int n) { vi ans; while (n % 2 == 0) {ans.pb(2);n = n / 2;} for (int i = 3; i <= sqrt(n); i = i + 2) { while (n % i == 0) {ans.pb(i);n = n / i;}} if (n > 2)ans.pb(n);return ans; } ll NcR(int n, int r) {long long p = 1, k = 1;if (n - r < r)r = n - r;if (r != 0) {while (r) {p *= n;k *= r; long long m = gcd(p, k);p /= m;k /= m;n--;r--;} }else p = 1;return p;// cout << p << endl; } bool sortasc(const rtri a,const rtri b) //Ascending ... change the argument accordingwise; { return a.second<b.second; } bool sortdesc(const int a,const int b) //Descending... change the argument accordingwise;a { return a>b; } int myceil(int num,int den) { return num%den == 0 ? num/den : num/den + 1; } int myfloor(int num,int den) { return num%den == 0 ? num/den : num/den - 1; } string to_str(char c) { return string(1, c); } // 2-D vector with both size--> vector<vector<int> > a(n, vector<int>(m)); #define pie 3.141592653589793238462643383279 const int N = 2e5 + 5; void ipgraph(int n, int m);void dfs(int u, int par);void bfs(int start);void iptree(int n); vi topological_sort(const vvi &a); //********************THE END OF TEMPLATES*******************// void q1(); vvi adj; vb visited(N); vpi edgelist; vi nodes; vi parent; int32_t main() { clock_t begin = clock(); fast(); #ifdef Local_Debug // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif test() { q1(); } return 0; } void q1() { int n; cin>>n; adj=vvi(n); edgelist=vpi(n-1); parent=vi(n); ipgraph(n,n-1); nodes=vi(n); int m; cin>>m; vi val; for (int i = 0; i < m; i++) { int a; cin>>a; val.pb(a); } while(sz(val)<n-1) val.pb(1); show(val); sort(all(val),greater<int>()); parent[0]=-1; dfs(0,-1); vi freq; show(edgelist); show(nodes); for (auto &&x : edgelist) { if(parent[x.F]!=x.S) { freq.pb(nodes[x.S]*(n-nodes[x.S])%M1); } else { freq.pb(nodes[x.F]*(n-nodes[x.F])%M1); } } sort(all(freq),greater<int>()); show(freq); int j=sz(val)-1; int ans=0; for (int i = sz(freq) - 1; i >= 1; i--) { ans=(ans+((freq[i]%M1)*(val[j--]%M1))%M1)%M1; } int temp=1; for (int i = j; i >= 0; i--) { temp=(temp*(val[i]%M1))%M1; } ans=(ans+(temp*freq[0])%M1)%M1; cout<<ans<<endl; } void iptree(int n){ //n is number of node for (int i = 0; i < n-1; i++){ //0-based index int a;cin>>a; adj[i+1].pb(a-1); adj[a-1].pb(i+1); } } void ipgraph(int n, int m){ //0-based index int i, u, v; int t=0; while(m--){ cin>>u>>v; u--, v--; edgelist[t++]={u,v}; adj[u].pb(v); adj[v].pb(u); } } void dfs(int u, int par){ // visited[u]=1; parent[u]=par; nodes[u]=1; for(int v:adj[u]){ if (v == par) continue; dfs(v, u); nodes[u]+=nodes[v]; } } void bfs(int start){ queue<int> Q; Q.push(start); visited[start]=1; while(!Q.empty()){ int v=Q.front(); Q.pop(); for (auto &&i : adj[v]){ if(!visited[i]) { visited[i]=1; Q.push(i); } } } } // Note: if there is a cycle, the size of the return will be less than n.(from neal template round 660) vector<int> topological_sort(const vector<vector<int>> &adj) { int n = (int)(adj.size()); vector<int> in_degree(n, 0); vector<int> order; for (int i = 0; i < n; i++) for (int neighbor : adj[i]) in_degree[neighbor]++; for (int i = 0; i < n; i++) if (in_degree[i] == 0) order.push_back(i); int current = 0; while (current < (int)order.size()) { int node = order[current++]; for (int neighbor : adj[node]) if (--in_degree[neighbor] == 0) order.push_back(neighbor); } return order; }
?
?
?
?