QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#37353 | #791. Mousetrap | MonkeyKing | 20 | 145ms | 71124kb | C++ | 2.9kb | 2022-07-01 11:02:13 | 2022-07-01 11:02:15 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define mt make_tuple
#define ull unsigned long long
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
const int inf=1039714778;
const int mod=1e9+7;
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
template <typename T> inline void chmin(T &x,const T &b) {x=min(x,b);}
template <typename T> inline void chmax(T &x,const T &b) {x=max(x,b);}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31) & mod;}
template <typename T>
ostream & operator << (ostream &cout,const vector<T> &v)
{
cout<<'{';
int fst=1;
for(auto x:v)
{
if(fst) fst=0;
else cout<<',';
cout<<x;
}
cout<<'}';
return cout;
}
template <typename T1,typename T2>
ostream & operator << (ostream &cout,const pair<T1,T2> &o)
{
cout<<'('<<o.first<<','<<o.second<<')';
return cout;
}
namespace FastIO
{
int cursor=(1<<20);
char buf[(1<<20)+5];
char getchar()
{
if(cursor==(1<<20))
{
cursor=0;
fread(buf,1,(1<<20),stdin);
}
return buf[cursor++];
}
int getnum()
{
char ch=0;
int res=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
{
res=res*10+ch-'0';
ch=getchar();
}
return res;
}
}
using FastIO::getnum;
int n,rt,src;
vector<int> edges[1000005];
int nxt[1000005];
int par[1000005];
void go(int x,int par)
{
::par[x]=par;
for(auto u:edges[x])
{
if(u==par) continue;
go(u,x);
}
}
int dp[1000005];
void dfs(int x,int cost)
{
for(auto u:edges[x])
{
if(u==par[x]) continue;
dfs(u,cost+(int)edges[x].size()-1-(nxt[x]!=-1));
}
if(nxt[x]!=-1) return;
vector<int> v;
v.reserve(edges[x].size());
for(auto u:edges[x])
{
if(u!=par[x]) v.emplace_back(dp[u]);
}
sort(all(v));
reverse(all(v));
if(!v.size())
{
dp[x]=cost;
}
else if(v.size()==1)
{
dp[x]=cost+1;
}
else
{
dp[x]=min(v[0],v[1]+1);
}
}
int check(int k)
{
int rm=0,used=0;
for(int x=src;x!=rt;x=par[x])
{
rm++;
int cnt=0;
for(auto u:edges[x])
{
if(u==par[x] || u==nxt[x]) continue;
if(dp[u]+used>k)
{
rm--;
cnt++;
}
}
if(rm<0) return false;
used+=cnt;
}
return (used<=k);
}
int main()
{
// freopen("input.txt","r",stdin);
n=getnum();rt=getnum();src=getnum();
rt--;src--;
if(rt==src)
{
puts("0");
return 0;
}
for(int i=0;i<n-1;i++)
{
int x=getnum(),y=getnum();
x--;y--;
edges[x].emplace_back(y);
edges[y].emplace_back(x);
}
go(rt,-1);
memset(nxt,-1,sizeof(nxt));
int x=src;
while(x!=rt)
{
nxt[par[x]]=x;
x=par[x];
}
dfs(nxt[rt],0);
int l=0,r=n,mid,res;
while(l<=r)
{
mid=l+r>>1;
if(check(mid))
{
res=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<res<<endl;
return 0;
}
详细
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 5ms
memory: 30872kb
input:
10 2 10 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 7ms
memory: 30900kb
input:
10 1 10 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 9ms
memory: 30868kb
input:
10 1 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 12ms
memory: 31000kb
input:
9 1 7 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 8ms
memory: 30972kb
input:
10 1 10 1 2 3 2 4 3 5 3 6 4 7 3 8 7 9 2 10 5
output:
3
result:
ok single line: '3'
Test #6:
score: 0
Accepted
time: 6ms
memory: 31024kb
input:
8 1 8 1 2 3 2 4 3 5 4 6 2 7 6 8 3
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 3ms
memory: 30940kb
input:
10 3 2 3 1 1 2 2 4 2 5 2 6 7 5 8 5 9 6 10 6
output:
5
result:
ok single line: '5'
Test #8:
score: 0
Accepted
time: 9ms
memory: 30904kb
input:
10 2 3 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 1 10
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 4ms
memory: 31052kb
input:
7 1 2 2 1 3 2 4 2 5 3 6 3 7 4
output:
3
result:
ok single line: '3'
Test #10:
score: 0
Accepted
time: 8ms
memory: 31048kb
input:
2 1 2 1 2
output:
0
result:
ok single line: '0'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 145ms
memory: 71124kb
input:
1000000 1 2 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 5...
output:
38
result:
wrong answer 1st lines differ - expected: '36', found: '38'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #17:
score: 20
Accepted
time: 14ms
memory: 30900kb
input:
43 2 5 1 2 1 3 3 4 4 5 5 11 11 12 11 13 4 9 6 9 9 14 9 15 9 16 4 10 10 17 10 18 10 19 10 20 8 21 8 22 8 23 8 24 8 25 8 26 8 27 8 28 8 29 8 30 1 8 7 1 7 31 7 32 7 33 7 34 7 35 7 36 7 37 7 38 7 39 7 40 9 41 10 42 10 43
output:
7
result:
ok single line: '7'
Test #18:
score: 0
Accepted
time: 0ms
memory: 31096kb
input:
1000 1 1000 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 5...
output:
9
result:
ok single line: '9'
Test #19:
score: 0
Accepted
time: 4ms
memory: 30940kb
input:
999 1 20 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
14
result:
ok single line: '14'
Test #20:
score: 0
Accepted
time: 4ms
memory: 31076kb
input:
1000 1 998 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 ...
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 4ms
memory: 31024kb
input:
901 1 901 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 3ms
memory: 31016kb
input:
1000 1 150 1 2 3 2 4 3 5 2 6 5 7 2 8 6 9 2 10 4 11 3 12 10 13 12 14 11 15 3 16 12 17 12 18 14 19 18 20 10 21 4 22 13 23 13 24 13 25 10 26 13 27 17 28 20 29 14 30 29 31 21 32 29 33 27 34 19 35 7 36 24 37 2 38 6 39 17 40 19 41 40 42 23 43 15 44 17 45 25 46 14 47 24 48 13 49 32 50 28 51 3 52 42 53 52 5...
output:
31
result:
ok single line: '31'
Test #23:
score: -20
Wrong Answer
time: 4ms
memory: 31048kb
input:
998 1 833 1 2 3 2 4 3 5 4 6 4 7 2 8 7 9 7 10 5 11 3 12 3 13 10 14 6 15 10 16 13 17 2 18 13 19 8 20 15 21 10 22 11 23 13 24 13 25 5 26 21 27 4 28 12 29 4 30 9 31 28 32 21 33 32 34 24 35 33 36 14 37 29 38 31 39 5 40 6 41 12 42 24 43 27 44 21 45 12 46 18 47 13 48 39 49 40 50 13 51 50 52 3 53 40 54 32 5...
output:
41
result:
wrong answer 1st lines differ - expected: '40', found: '41'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%