QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #207832 | #5157. High-quality Tree | Minhho | Compile Error | / | / | C++20 | 5.2kb | 2023-10-08 21:11:49 | 2023-10-08 21:11:50 |
Judging History
answer
#define taskname "H"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5 + 10;
vector<int> adj[maxn];
set<ii> mp[maxn];
int n, m, dp[maxn], dep[maxn], pa[maxn], ans = 0;
void DFS(int u = 1, int p = 0)
{
bool f = ((u == 1 && adj[u].size() == 1) || (u != 1 && adj[u].size() == 2));
for (int v: adj[u]) if (v != p)
{
dep[v] = dep[u] + 1;
pa[v] = u;
DFS(v, u);
assert(!mp[v].empty());
if (mp[u].empty())
{
swap(mp[u], mp[v]);
if (f)
{
int mnu = dep[u], mxu = (--mp[u].end())->ff;
while ((mxu - mnu) > 1)
{
ii ed = *(--mp[u].end());
ans++;
mp[u].erase(ed);
ed.ss = pa[ed.ss];
ed.ff--;
mp[u].emplace(ed);
mxu = (--mp[u].end())->ff;
}
}
}
else
{
if (mp[u].size() > mp[v].size())
for (auto [x, y]: mp[v]) mp[u].emplace(x, y);
else
{
for (auto [x, y]: mp[u]) mp[v].emplace(x, y);
swap(mp[u], mp[v]);
}
int mnu = mp[u].begin()->ff, mxu = (--mp[u].end())->ff;
while ((mxu - mnu) > 1)
{
ii ed = *(--mp[u].end());
ans++;
mp[u].erase(ed);
ed.ss = pa[ed.ss];
ed.ff--;
mp[u].emplace(ed);
mxu = (--mp[u].end())->ff;
mnu = mp[u].begin()->ff;
}
}
}
if (mp[u].empty()) mp[u].emplace(dep[u], u);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n;
for (int i=1, u, v; i<n; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u);
DFS();
cout<<ans;
}
/**
9
1 2
1 3
2 4
2 5
4 6
4 7
5 8
5 9
**/
#define taskname "H"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5 + 10;
vector<int> adj[maxn];
set<ii> mp[maxn];
int n, m, dp[maxn], dep[maxn], lz[maxn], pa[maxn];
void DFS(int u = 1, int p = 0)
{
bool f = ((u == 1 && adj[u].size() == 1) || (u != 1 && adj[u].size() == 2));
for (int v: adj[u]) if (v != p)
{
dep[v] = dep[u] + 1, pa[v] = u;
DFS(v, u);
dp[u] += dp[v];
assert(!mp[v].empty());
if (mp[u].empty())
{
if (!f)
{
swap(mp[u], mp[v]), lz[u]=lz[v];
// if (u == 1)
// for (auto [x, y]: mp[u]) cerr<<"WWWWW: "<<x<<" "<<y<<"\n";
}
else
{
int mnu = 0, mxv = (--mp[v].end())->ff + lz[v];
while ((mxv - mnu) > 1)
{
ii ed = *(--mp[v].end());
// cerr<<v<<" "<<mxv<<" AND: "<<u<<" "<<mnu<<"\n";
dp[u]++;
mp[v].erase(ed);
ed.ss = pa[ed.ss];
ed.ff--;
mp[v].emplace(ed);
mxv = (mp[v].empty() ? 0 : (--mp[v].end())->ff + lz[v]);
}
swap(mp[u], mp[v]), lz[u] = lz[v];
}
}
else
{
int mxu = (--mp[u].end())->ff + lz[u], mxv = (--mp[v].end())->ff + lz[v];
while ((mxv - mxu) > 1)
{
ii ed = *(--mp[v].end());
// cerr<<v<<" "<<mxv<<" AND: "<<u<<" "<<mnu<<"\n";
dp[u]++;
mp[v].erase(ed);
ed.ss = pa[ed.ss];
ed.ff--;
mp[v].emplace(ed);
mxv = (--mp[v].end())->ff + lz[v];
}
while ((mxu - mxv) > 1)
{
ii ed = *(--mp[u].end());
// cerr<<v<<" "<<mxv<<" AND: "<<u<<" "<<mnu<<"\n";
dp[u]++;
mp[u].erase(ed);
ed.ss = pa[ed.ss];
ed.ff--;
mp[u].emplace(ed);
mxu = (--mp[u].end())->ff + lz[u];
}
if (mp[u].size() > mp[v].size())
for (auto [x, y]: mp[v]) mp[u].emplace(x+lz[v]-lz[u], y);
else
{
for (auto [x, y]: mp[u]) mp[v].emplace(x+lz[u]-lz[v], y);
lz[u] = lz[v];
swap(mp[u], mp[v]);
}
}
}
if (mp[u].empty()) mp[u].emplace(0, u), lz[u] = 0;
lz[u]++;
// cerr<<"DP: "<<u<<" "<<lz[u]<<" "<<dp[u]<<"\n";
// cerr<<"CUR: \n";
// for (auto [x, y]: mp[u]) cerr<<x<<" "<<y<<"\n";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin>>n;
for (int i=1, u, v; i<n; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u);
DFS();
cout<<dp[1];
}
Details
answer.code:93:11: error: redefinition of ‘const int maxn’
93 | const int maxn = 2e5 + 10;
| ^~~~
answer.code:8:11: note: ‘const int maxn’ previously defined here
8 | const int maxn = 2e5 + 10;
| ^~~~
answer.code:94:13: error: redefinition of ‘std::vector<int> adj [200010]’
94 | vector<int> adj[maxn];
| ^~~
answer.code:9:13: note: ‘std::vector<int> adj [200010]’ previously declared here
9 | vector<int> adj[maxn];
| ^~~
answer.code:95:9: error: redefinition of ‘std::set<std::pair<int, int> > mp [200010]’
95 | set<ii> mp[maxn];
| ^~
answer.code:10:9: note: ‘std::set<std::pair<int, int> > mp [200010]’ previously declared here
10 | set<ii> mp[maxn];
| ^~
answer.code:96:5: error: redefinition of ‘int n’
96 | int n, m, dp[maxn], dep[maxn], lz[maxn], pa[maxn];
| ^
answer.code:11:5: note: ‘int n’ previously declared here
11 | int n, m, dp[maxn], dep[maxn], pa[maxn], ans = 0;
| ^
answer.code:96:8: error: redefinition of ‘int m’
96 | int n, m, dp[maxn], dep[maxn], lz[maxn], pa[maxn];
| ^
answer.code:11:8: note: ‘int m’ previously declared here
11 | int n, m, dp[maxn], dep[maxn], pa[maxn], ans = 0;
| ^
answer.code:96:11: error: redefinition of ‘int dp [200010]’
96 | int n, m, dp[maxn], dep[maxn], lz[maxn], pa[maxn];
| ^~
answer.code:11:11: note: ‘int dp [200010]’ previously declared here
11 | int n, m, dp[maxn], dep[maxn], pa[maxn], ans = 0;
| ^~
answer.code:96:21: error: redefinition of ‘int dep [200010]’
96 | int n, m, dp[maxn], dep[maxn], lz[maxn], pa[maxn];
| ^~~
answer.code:11:21: note: ‘int dep [200010]’ previously declared here
11 | int n, m, dp[maxn], dep[maxn], pa[maxn], ans = 0;
| ^~~
answer.code:96:42: error: redefinition of ‘int pa [200010]’
96 | int n, m, dp[maxn], dep[maxn], lz[maxn], pa[maxn];
| ^~
answer.code:11:32: note: ‘int pa [200010]’ previously declared here
11 | int n, m, dp[maxn], dep[maxn], pa[maxn], ans = 0;
| ^~
answer.code:98:6: error: redefinition of ‘void DFS(int, int)’
98 | void DFS(int u = 1, int p = 0)
| ^~~
answer.code:13:6: note: ‘void DFS(int, int)’ previously defined here
13 | void DFS(int u = 1, int p = 0)
| ^~~
answer.code:174:8: error: redefinition of ‘int main()’
174 | signed main()
| ^~~~
answer.code:66:8: note: ‘int main()’ previously defined here
66 | signed main()
| ^~~~