QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710442 | #9230. Routing K-Codes | Drimpossible | WA | 184ms | 48284kb | C++14 | 4.8kb | 2024-11-04 19:52:22 | 2024-11-04 19:52:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader(){}
} cin;
const char endl = '\n';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
#define int __int128
#define NO return cout<<"NIE",0
const int N=2e5+5;
int n,m,rt;
vector<int>e[N];
int dep[N],mx[2][N],cnt[N];
int f[N],g[N],mn[2][N];
void getdep(int u,int fa){
for(int v:e[u]){
if(v==fa)continue;
dep[v]=dep[u]+1;
getdep(v,u);
if(mx[0][v]+1>mx[0][u])
mx[1][u]=mx[0][u],mx[0][u]=mx[0][v]+1;
else mx[1][u]=max(mx[1][u],mx[0][v]+1);
}
}
void getmx(int u,int fa){
for(int v:e[u]){
if(v==fa)continue;
int val=mx[0][u]+1;
if(mx[0][v]+1==mx[0][u])val=mx[1][u]+1;
if(val>mx[0][v])
mx[1][v]=mx[0][v],mx[0][v]=val;
else mx[1][v]=max(mx[1][v],val);
getmx(v,u);
}
}
void dfs(int u,int fa){
f[u]=1;
for(int v:e[u]){
if(v==fa)continue;
cnt[u]++;
dfs(v,u);
f[u]+=(f[v]<<1);
g[u]+=g[v]+f[v];
if(f[v]>mn[0][u])
mn[1][u]=mn[0][u],mn[0][u]=f[v];
else mn[1][u]=max(mn[1][u],f[v]);
}
g[u]-=mn[0][u];
}
void fds(int u,int fa){
for(int v:e[u]){
if(v==fa)continue;
int val=g[u]+mn[0][u]-g[v]-f[v];
if(mn[0][u]==f[v])val-=mn[1][u];
else val-=mn[0][u];
g[v]+=val;
val=(f[u]-f[v]*2);
// cout<<v<<' '<<val<<'\n';
g[v]+=val,f[v]+=val*2;
g[v]+=mn[0][v];
if(val>mn[0][v])
mn[1][v]=mn[0][v],mn[0][v]=val;
else mn[1][v]=max(mn[1][v],val);
g[v]-=mn[0][v];
fds(v,u);
}
}
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin>>n>>m;
if(m>n-1)NO;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
for(int i=1;i<=n;i++)
if(e[i].size()>3)NO;
getdep(1,0),getmx(1,0);
mx[0][0]=1e18;
for(int i=1;i<=n;i++)
if(mx[0][i]<mx[0][rt]&&e[i].size()<3)rt=i;
if(mx[0][rt]>31)NO;
// cout<<rt<<'\n';
dfs(rt,0);
// for(int i=1;i<=n;i++)
// cout<<f[i]<<' '<<g[i]<<'\n';
// cout<<f[2]<<"\n";
fds(rt,0);
int ans=1e18;
for(int i=1;i<=n;i++){
if(e[i].size()==3)continue;
if(e[i].size()==1){
if(mx[0][i]>31)continue;
int u=e[i][0];
ans=min(ans,g[u]+f[u]-3);
}
else {
if(mx[0][i]>30)continue;
ans=min(ans,f[i]+g[i]);
}
}
if(ans>=1e18)NO;
cout<<ans;
return 0;
}
/*
10 9
3 4
6 7
5 6
3 5
2 3
2 8
1 2
9 10
1 9
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 17824kb
input:
4 3 1 2 1 3 1 4
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9660kb
input:
4 6 1 2 2 3 3 4 4 1 1 3 2 4
output:
NIE
result:
ok single line: 'NIE'
Test #3:
score: 0
Accepted
time: 2ms
memory: 11932kb
input:
10 10 9 3 5 10 1 4 10 8 8 3 7 3 9 6 8 6 7 2 4 5
output:
NIE
result:
ok single line: 'NIE'
Test #4:
score: 0
Accepted
time: 108ms
memory: 31980kb
input:
200000 199999 172774 188052 195063 155577 38023 148303 30605 155047 170238 19344 46835 58255 154268 109062 197059 116041 136424 12058 42062 149807 109545 115380 132322 51106 16706 162612 62234 31319 195735 80435 173898 84051 19876 102910 186924 9136 123094 117097 145054 173049 137364 152731 82662 18...
output:
NIE
result:
ok single line: 'NIE'
Test #5:
score: 0
Accepted
time: 178ms
memory: 47636kb
input:
200000 199999 168192 30733 164413 46673 175210 2329 69389 67102 33991 152553 91061 55265 166724 117726 90148 157176 34831 12213 60756 105488 121891 155192 82202 155666 102083 156661 38968 75200 190004 107321 72436 92732 64314 65004 39210 91106 70455 173568 179742 29844 126232 19552 133509 110602 131...
output:
20980030044349
result:
ok single line: '20980030044349'
Test #6:
score: 0
Accepted
time: 0ms
memory: 17836kb
input:
4 3 1 2 1 3 1 4
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 100ms
memory: 31888kb
input:
199021 199020 189105 111001 147300 187047 67395 102319 25317 152109 56495 115535 11656 19974 119178 6528 84571 159100 198873 156684 21161 163040 91720 165273 168305 140152 104884 119802 131 177991 35930 74934 27528 278 177640 162738 118439 69472 20365 85043 184995 54207 64542 188847 97881 167717 188...
output:
NIE
result:
ok single line: 'NIE'
Test #8:
score: 0
Accepted
time: 162ms
memory: 47168kb
input:
200000 199999 145608 31176 94180 155303 112924 85699 196865 176102 34049 30841 84924 191665 164317 97582 10102 125492 114493 20622 127660 194591 183851 21461 167689 53839 59189 126425 135853 79950 173910 4196 8134 182272 42157 63799 5109 182005 197391 154014 93467 130380 1508 66644 129681 199910 677...
output:
25146839515965
result:
ok single line: '25146839515965'
Test #9:
score: 0
Accepted
time: 184ms
memory: 48284kb
input:
200000 199999 160386 189041 24452 73297 75992 87415 87012 116413 18645 2219 151007 100916 87623 77520 51217 45179 51633 67938 183428 99891 74684 129965 186795 70345 28743 22633 107782 28087 117185 78477 46846 176763 18968 80952 118201 35872 123906 140127 65784 66684 24802 134847 42591 150517 27123 1...
output:
9894117829832
result:
ok single line: '9894117829832'
Test #10:
score: -100
Wrong Answer
time: 129ms
memory: 31520kb
input:
200000 199999 42958 26294 73743 94861 161036 525 22581 6649 152064 106483 126795 178801 147721 107972 43433 197974 75281 163319 170596 167054 180443 168322 1443 163261 197722 164837 144573 16585 6005 143774 195029 188032 112864 105465 108330 154314 138435 103667 66734 146178 15416 123293 22322 10216...
output:
NIE
result:
wrong answer 1st lines differ - expected: '28756428378750', found: 'NIE'