QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#500899 | #5502. Dazzling Mountain | Sakib_Safwan | TL | 8556ms | 216792kb | C++20 | 3.7kb | 2024-08-01 23:41:57 | 2024-08-01 23:41:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
// #define int long long
// Don't Start typing till you complete the idea.
// Check these things for WA and before submitting
// 1. Did you clear all the global arrays
// 2. Did you checked your <= >= < >
// 3. Did you take the input properly. Did you use break or return while taking input?
// 4. Did you divide by 0.
// 5. Check array , vector , etc size
// 6. in the while loop did you miss something that would cause infinite loop?
// 7. Did you save your dp?
// 8. Are you trying to use something after deleting it?
// 9. Did you read the problem statement wrong?
// 10. Did you check the constrains of the problem properly
// 11. Did you checked for smaller cases like 1 , 0 , etc
// 12. Is it something to with overflow?
// 13. Did you initialized all the variables properly?
// 14. Did you use the formulas correctly?
// STRESS TESTING !!!!!! STRESS TESTING !!!!!
// STRESS Testing Not working?
// Stress test for multiple cases?
// Stress test for big inputs?
// Stress test for really small inputs?
// Even then if it doesn't work -> Did you wrote the wrong Brute force code
// Check these things if you are not generating ideas
// 1. Did you try thinking it in reverse?
// 2. Read the problem statement again
// 3. Check the constraints again
// 4. Try smaller cases in notebook and try to expand
// 5. Think about invariants
// 6. Think simpler ideas maybe?
// 7. Think brute force and try to get something out of it.
// 8. Maybe take a deep breath and take a break for few minutes and drink some water? :3
const int N = 1e6 + 3;
vector<int> adj[N];
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
gp_hash_table<int, int, custom_hash> st[N];
int sz[N];
int small[N];
void dfs(int u , int p = 0){
sz[u] = 1;
int mnv = N;
small[u] = -1;
for(auto x : adj[u]){
if(x == p) continue;
dfs(x , u);
sz[u] += sz[x];
if(mnv > sz[x]) mnv = sz[x] , small[u] = x;
}
if(small[u] != -1) swap(st[small[u]] , st[u]);
vector<int> bad;
for(auto x : st[u]){
for(auto y : adj[u]){
if(y == small[u] || y == p) continue;
if(st[y].find(x.first) == st[y].end()) {
// cout << y << ' ' << small[u] << ' ' << x.first << endl;
bad.pb(x.first);
break;
}
}
}
for(auto x : bad) st[u].erase(x);
st[u][sz[u]] = 1;
// cout << u << endl;
// for(auto x : st[u]) cout << x.first << ' ' << x.second << endl;
}
void GG()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++){
adj[i].clear();
st[i].clear();
sz[i] = 0;
}
for(int i = 2; i <= n; i++){
int x , y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(1);
cout << st[1].size() << endl;
vector<int> lst;
for(auto x : st[1]) lst.pb(x.first);
sort(all(lst));
for(auto x : lst) cout << x << ' ';
cout << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ttc=1;
cin>>ttc;
//int cnt=0;
while(ttc--)
{
//cout<<"Case "<<++cnt<<": ";
GG();
}
}
详细
Test #1:
score: 100
Accepted
time: 59ms
memory: 216468kb
input:
1 9 1 2 2 3 3 4 3 5 2 6 6 7 7 8 7 9
output:
4 1 3 8 9
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 8556ms
memory: 216792kb
input:
10000 906 675 189 555 889 491 97 791 419 175 694 713 842 788 513 159 354 670 815 652 546 253 87 89 278 563 429 522 900 202 657 331 865 35 605 735 532 612 471 657 386 7 886 856 164 224 777 73 534 481 631 711 698 240 465 115 181 191 825 311 155 709 501 207 849 294 546 591 682 96 405 210 696 861 13 781...
output:
63 1 3 4 34 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 6 1 2 3 4 5 11 28 1 2 3 4 5 6 15 16 17 18 19 20 21...
result:
ok 20000 lines
Test #3:
score: -100
Time Limit Exceeded
input:
10 257056 71485 24974 175037 254578 15503 255561 2268 184070 101954 23776 151400 163190 209539 157934 61908 8578 251032 109510 106012 63219 6393 135129 229530 202665 135202 195080 36226 54716 113653 27375 130515 126621 51348 62149 190321 116509 235895 205631 193944 184367 234172 88847 217084 158554 ...