QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #620771 | #9230. Routing K-Codes | free_windy | Compile Error | / | / | C++20 | 3.9kb | 2024-10-07 21:07:55 | 2024-10-07 21:07:56 |
Judging History
answer
//utl
#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read(){
int s=0,z=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')z=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*z;
}
const int N = 2e5+5;
long long fr[N],to[N*2],nt[N*2],cnt;
long long n,m;
long long r[N];
long long son[N][2];
bool vis[N];
bool sf;
int ts[N],f[N],rts[N];
long long deep[N];
int ans;
bool vis2[N];
int root;
void ct(long long x,long long y){
nt[++cnt]=fr[x];
fr[x]=cnt;
to[cnt]=y;
return ;
}
int wz(long long x,long long y){
return y==son[x][1];
}//fa ->son
void dfs2(long long x,long long fa){
int tot=0;
f[x]=fa;
rts[x]=1;
deep[x]=1;
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa) continue;
dfs2(to[i],x);
rts[x]+=rts[to[i]]*2;
son[x][tot++]=to[i];
deep[x]=max(deep[x],deep[to[i]]+1);
}
ts[x]=ts[son[x][1]]+rts[son[x][1]]+ts[son[x][0]]+rts[son[x][0]]+min(rts[son[x][1]],rts[son[x][0]])+1;
return ;
}
void write(int x){
long long s1=x%10;
if(x>=10)write(x/10);
cout<<s1;
}
void dfs(int x,int fa){
deep[x]=deep[fa]+1;
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa) continue;
dfs(to[i],x);
}
return ;
}
void find_dep(int x,int fa){
if(r[x]<3){
deep[x]=max(deep[x],deep[fa]+1);
if(deep[x]<32&&!root){
root=x;
return ;
}
}
int ks[2],wks;
ks[0]=ks[1]=0;
int tot=0;
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa) continue;
ks[++tot]=i;
}
for(int i=fr[x];i;i=nt[i]){
if(to[i]==fa) continue;
if(to[i]==ks[1]) wks=1;
else wks=0;
deep[x]=max(deep[fa],deep[wks^1])+1;
find_dep(to[i],x);
}
deep[x]=max(deep[ks[0]],deep[ks[1]])+1;
return ;
}
void cg(long long x){
vis2[x]=1;
if(r[x]==1){
int y=to[fr[x]];
if(deep[y]>32) return ;
if(deep[y]<32)ans=min(ans,ts[y]);
ts[x]=1;
rts[x]=1;
deep[x]=1;
for(int i=fr[x];i;i=nt[i]){
if(vis2[to[i]]) continue;
cg(to[i]);
}
return ;
}
if(r[x]==2){
if(f[x]!=0)rts[x]=1+(rts[son[x][0]]+rts[f[x]])*2,ts[x]=(ts[son[x][0]]+ts[f[x]])+rts[son[x][0]]+rts[f[x]]+min(rts[son[x][0]],rts[f[x]])+1,deep[x]=max(deep[son[x][0]],deep[f[x]])+1;
else rts[x]=1+(rts[son[x][0]]+rts[son[x][1]])*2,ts[x]=(ts[son[x][0]]+ts[son[x][1]])+rts[son[x][0]]+rts[son[x][1]]+min(rts[son[x][0]],rts[son[x][1]])+1,deep[x]=max(deep[son[x][0]],deep[son[x][1]])+1;
if(deep[x]>=32) return ;
if(deep[x]<32)ans=min(ans,ts[x]);
for(int i=fr[x];i;i=nt[i]){
if(vis2[to[i]]) continue;
int sw=wz(x,to[i]);
rts[x]=1+(rts[son[x][sw^1]]+rts[f[x]])*2;
deep[x]=max(deep[son[x][sw^1]],deep[f[x]])+1;
ts[x]=ts[son[x][sw^1]]+rts[son[x][sw^1]]+ts[f[x]]+rts[f[x]]+min(rts[f[x]],rts[son[x][sw^1]])+1;
cg(to[i]);
}
deep[x]=max(deep[son[x][0]],deep[son[x][1]])+1;
rts[x]=1+(rts[son[x][0]]+rts[son[x][1]])*2;
ts[x]=ts[son[x][0]]+rts[son[x][0]]+ts[son[x][1]]+rts[son[x][1]]+min(rts[son[x][1]],rts[son[x][0]])+1;
return ;
}
for(int i=fr[x];i;i=nt[i]){
if(vis2[to[i]]) continue;
int sw=wz(x,to[i]);
rts[x]=1+(rts[son[x][sw^1]]+rts[f[x]])*2;
deep[x]=max(deep[son[x][sw^1]],deep[f[x]])+1;
ts[x]=ts[son[x][sw^1]]+rts[son[x][sw^1]]+ts[f[x]]+rts[f[x]]+min(rts[f[x]],rts[son[x][sw^1]])+1;
cg(to[i]);
}
deep[x]=max(deep[son[x][0]],deep[son[x][1]])+1;
rts[x]=1+(rts[son[x][0]]+rts[son[x][1]])*2;
ts[x]=ts[son[x][0]]+rts[son[x][0]]+ts[son[x][1]]+rts[son[x][1]]+min(rts[son[x][1]],rts[son[x][0]])+1;
return ;
}
signed main(){
// freopen("slt.in","r",stdin);
// freopen("my.out","w",stdout);
n=read(),m=read();
ans=1e18;
for(int x,y,i=1;i<=m;i++){
x=read(),y=read();
r[x]++;
r[y]++;
if(r[x]>3||r[y]>3){
cout<<"NIE";
return 0;
}
ct(x,y);
ct(y,x);
}
if(m!=n-1){
cout<<"NIE";
return 0;
}
dfs(1,0);
find_dep(1,0);
if(root==0){
cout<<"NIE";
return 0;
}
dfs2(root,0);
cg(root);
if(ans==1e18){
cout<<"NIE";
return 0;
}
if(n>=20000)cout<<root<<"\n";
write(ans);
return 0;
}
Details
answer.code: In function ‘int main()’:
answer.code:171:25: error: ambiguous overload for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘__int128’)
171 | if(n>=20000)cout<<root<<"\n";
| ~~~~^~~~~~
| | |
| | __int128
| std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/13/bits/unique_ptr.h:42,
from /usr/include/c++/13/memory:78,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:56,
from answer.code:2:
/usr/include/c++/13/ostream:168:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
168 | operator<<(long __n)
| ^~~~~~~~
/usr/include/c++/13/ostream:172:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
172 | operator<<(unsigned long __n)
| ^~~~~~~~
/usr/include/c++/13/ostream:176:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
176 | operator<<(bool __n)
| ^~~~~~~~
In file included from /usr/include/c++/13/ostream:880:
/usr/include/c++/13/bits/ostream.tcc:96:5: note: candidate: ‘std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]’
96 | basic_ostream<_CharT, _Traits>::
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:183:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
183 | operator<<(unsigned short __n)
| ^~~~~~~~
/usr/include/c++/13/bits/ostream.tcc:110:5: note: candidate: ‘std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]’
110 | basic_ostream<_CharT, _Traits>::
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/ostream:194:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
194 | operator<<(unsigned int __n)
| ^~~~~~~~
/usr/include/c++/13/ostream:203:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
203 | operator<<(long long __n)
| ^~~~~~~~
/usr/include/c++/13/ostream:207:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
207 | operator<<(unsigned long long __n)
| ^~~~~~~~
/usr/include/c++/13/ostream:222:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
222 | operator<<(double __f)
| ^~~~~~~~
/usr/include/c++/13/ostream:226:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
226 | operator<<(float __f)
| ^~~~~~~~
/usr/include/c++/13/ostream:234:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; __ostream_type = std::basic_ostream<char>]’
234 | operator<<(long double __f)
| ^~~~~~~~
/usr/include/c++/13/ostream:564:5: note: candidate: ‘std::basic_ostream<_CharT, _Traits>& std::operator<<(basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = char_traits<char>]’
564 | operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
| ^~~~~~~~
/usr/include/c++/13/ostream:570:5: note: candidate: ‘std::basic_ostream<char, _Traits>& std::operator<<(b...