QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #147456 | #6503. DFS Order 3 | Scene | WA | 34ms | 3640kb | C++14 | 2.6kb | 2023-08-23 10:02:27 | 2023-08-25 01:31:49 |
Judging History
answer
#include<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
int T;
int e[1050][1050],n;
int bcj[1050],ans;
int vis[1050];
int root(int x)
{
return x==bcj[x]? x:bcj[x]=root(bcj[x]);
}
int main(){
read(T);
while(T--)
{
read(n); for(int i=1;i<=n;i++) bcj[i]=i;
memset(vis,0,sizeof(vis)); ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
read(e[i][j]);
for(int i=1;i<=n;i++)
{
if(root(e[i][1])!=root(e[i][2]))
{
bcj[root(e[i][1])]=root(e[i][2]); ans++;
write(e[i][1]),pc(' '),write(e[i][2]),pc('\n');
}
}
if(ans==n-1) continue;
for(int o=n;o>=1;o--)
{
pc('\n');
for(int i=1;i<=n;i++)
{
int u=e[i][o],v=e[u][2],id=0;
if(vis[u]) continue;
for(int j=1;j<=n;j++)
{
if(e[v][j]==u)
{
id=j;
break;
}
}int j=2;
for(;j<=id;j++)
{
if(j==2&&root(e[v][1])!=root(e[v][2]))
{
bcj[root(e[v][1])]=root(e[v][2]); ans++;
write(e[v][1]),pc(' '),write(e[v][2]),pc('\n');
}
if(root(e[v][1])!=root(e[v][j])) break;
}
if(j==id+1&&id!=n)
{
if(root(e[v][1])!=root(e[v][j]))
{
bcj[root(e[v][1])]=root(e[v][j]); ans++;
write(e[v][1]),pc(' '),write(e[v][j]),pc('\n');
break;
}
}
}
if(ans==n-1) break;
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
4 2 1 2 2 1 3 1 2 3 2 1 3 3 2 1 4 1 2 3 4 2 1 3 4 3 2 4 1 4 2 1 3 5 1 2 4 3 5 2 4 1 3 5 3 5 1 2 4 4 2 1 3 5 5 3 1 2 4
output:
1 2 1 2 3 2 1 2 3 2 4 2 1 2 2 4 3 5 3 1
result:
ok correct answer! (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 34ms
memory: 3640kb
input:
20000 10 1 2 4 5 6 7 3 8 10 9 2 1 4 5 6 7 3 8 10 9 3 8 1 2 4 5 6 7 10 9 4 5 6 7 1 2 3 8 10 9 5 4 6 7 1 2 3 8 10 9 6 7 4 5 1 2 3 8 10 9 7 6 4 5 1 2 3 8 10 9 8 3 1 2 4 5 6 7 10 9 9 10 1 2 4 5 6 7 3 8 10 1 2 4 5 6 7 3 8 9 10 1 4 3 8 2 9 6 5 7 10 2 8 9 6 3 4 1 5 7 10 3 8 2 9 6 4 1 5 7 10 4 1 3 8 2 9 6 5...
output:
1 2 3 8 4 5 6 7 9 10 10 1 3 1 6 4 1 4 1 4 2 8 3 8 5 4 6 9 7 5 10 7 9 8 4 3 1 9 2 4 3 10 5 6 7 5 8 2 5 9 2 10 1 6 2 4 3 8 5 7 9 6 10 2 8 7 2 6 6 7 1 9 2 10 3 6 4 7 5 1 8 9 10 3 3 7 1 7 1 10 2 6 3 8 4 8 5 10 7 9 9 8 2 10 1 10 2 3 3 7 4 8 5 8 6 7 9 2 10 2 8 7 1...
result:
wrong answer your output is not a tree (test case 3)