QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182865#5407. 基础图论练习题FLY0 128ms111248kbC++144.9kb2023-09-18 17:36:022023-09-18 17:36:02

Judging History

你现在查看的是最新测评结果

  • [2023-09-18 17:36:02]
  • 评测
  • 测评结果:0
  • 用时:128ms
  • 内存:111248kb
  • [2023-09-18 17:36:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define dFor(i,a,b) for(int i=(a);i>=(b);i--)
#define abs_(x) max(x,-(x))
#define tomin(x,y) x=min(x,y)
#define tomax(x,y) x=max(x,y)
#define eq(x,y) (abs_((x)-(y))<=eps) 
#define db double
#define pw(x) ((x)*(x))
#define y1 __
#define vci vector<int> 
#define pb push_back
#define all(x) x.begin(),x.end()
constexpr int N=5e3+5,P=1e9+7;
int read()
{	
	int x=0,y=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') y=0;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	return y?x:-x;
}
char getc()
{
	char c=getchar();
	for(;!isdigit(c)&&!isalpha(c);c=getchar()) ;
	return c;
}
int turn(char t)
{
	if(isdigit(t)) return t-'0';
	return t-'A'+10;
}
int n;
bool e[N][N];
vector<int> scc[N];
vector<int> e2[N];
int bel[N];
int stk[N],dfn[N],low[N],tot,ct,ct2;
bool vs[N];
int ans[N][N];
void tarjan(int u)
{
//	cout<<"<<"<<u<<"  "<<dfn[u]<<endl;
	vs[u]=1;
	dfn[u]=low[u]=++tot;
	stk[++ct]=u;
	For(v,1,n) if(e[u][v])
	{
		if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); }
		else if(vs[v]) low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u])
	{
		ct2++;
		do
		{
			int v=stk[ct--];
			vs[v]=0;
			bel[v]=ct2;
			scc[ct2].pb(v);
		}while(stk[ct+1]!=u);
	}
}
int cid[N];
int rd[N];
int q[N];
int Sum;
void tarjan2(int u)
{
	vs[u]=1;
	dfn[u]=low[u]=++tot;
	stk[++ct]=u;
	For(v,1,n) if(e[u][v])
	{
		if(!dfn[v]) { tarjan2(v); low[u]=min(low[u],low[v]); }
		else if(vs[v]) low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u])
	{
		ct2++;
		do
		{
			int v=stk[ct--];
			vs[v]=0; Sum++;
		}while(stk[ct+1]!=u);
	}
}
void cls()
{
	tot=ct=ct2=0;
	memset(vs,0,n+2);
	memset(dfn,0,n+2<<2);
}
void solve(vector<int> nw)
{
//	cout<<"A";
	int sz=nw.size();
//	cout<<"  "<<sz<<endl;
//	For(i,0,sz-1) cout<<nw[i]<<" "; puts("");
	vector<int> h;
	for(int u:nw)
	{
		if(h.empty()) { h.pb(u); continue; }
		if(e[u][h[0]]) { h.insert(h.begin(),u); continue; }
		if(e[h.back()][u]) { h.pb(u); continue; }
		for(int i=0;i<h.size()-1;i++)
		{
			if(e[h[i]][u]&&e[u][h[i+1]])
			{
				h.insert(h.begin()+i+1,u);
				break;
			}
		}
	}
//	cout<<"B";
//	for(int u:h) cout<<u<<" "; puts("");
	int t=0;
	if(sz==1) goto ok; 
	for(int i=1;;i++)
	{
		if(e[h[i]][h[0]]) { t=i; break; }
	}
	for(int i=t+1;i<sz;i++)
	{
		For(j,0,t)
		{
			if(e[h[i]][h[j]])
			{
				vector<int> ls;
				For(l,j,t) ls.pb(h[l]);
				For(l,0,j-1) ls.pb(h[l]);
				For(l,t+1,i) ls.pb(h[l]);
				For(l,0,i) h[i]=ls[i];
				t=i;
				break;
			}
		}
	}
//	cout<<"C";
//	for(int i=0;i<sz;i++)
//	{
//		int u=h[i],v=h[(i+1)%sz];
//		if(!e[u][v]) puts("FLY");
//	}
	ok: ;
//	return;
	For(i,0,sz-1)
	{
		int u=h[i],v=h[(i+1)%sz];
		e[u][v]=0,e[v][u]=1;
		cls();
		Sum=0;
		For(u,1,n) if(!dfn[u]) tarjan2(u);
		ans[u][v]=Sum;
		e[u][v]=1,e[v][u]=0;
	}
//	cout<<"D";
}
int h[N][N];
int pw2[N*N];
int work()
{
	n=read();
	For(i,1,n) For(j,1,n) e[i][j]=h[i][j]=0;
	For(i,1,n) scc[i].clear();
	For(i,1,n) e2[i].clear();
	
//	int m=n*(n-1)/2;
//	For(i,1,m)
//	{
//		int u=read(),v=read();
//		e[u][v]=1;
//	}
	
	For(i,1,n-1)
	{
		int up=(i+3)>>2;
		For(j,1,up)
		{
			int t=turn(getc()); 
			For(k,0,3)
			{
				bool tt=t>>k&1;
				int t1=i+1,t2=4*j+k-3;
				if(t2<t1)
				{
					if(tt) e[t1][t2]=1;
					else e[t2][t1]=1;
				}
			}
		}
	}
//	For(i,1,n)
//	{
//		For(j,1,n) putchar(e[i][j]+'0'); puts("");
//	}
	cls();
//	puts("FLY");
	For(i,1,n) if(!dfn[i]) tarjan(i);
//	puts("SKY");
	memset(rd,0,n+2<<2);
	For(u,1,n)
	{
		For(v,1,n) if(e[u][v]&&bel[u]!=bel[v])
		{
			int t1=bel[u],t2=bel[v];
			h[t1][t2]++;
			e2[t1].pb(t2);
			rd[t2]++;
		}
	}
	int l=1,r=0;
	For(i,1,ct2) if(!rd[i]) q[++r]=i;
	while(l<=r)
	{
		int u=q[l++];
		cid[u]=l-1;
		for(auto v:e2[u])
		{
			rd[v]--;
			if(!rd[v]) q[++r]=v;
		}
	}
//	cout<<ct2<<endl;
//	puts("RUI");
	For(i,1,n) For(j,1,n) ans[i][j]=ct2;
//	For(i,1,r) cout<<bel[q[i]]<<" "; puts("");
	For(i,1,n) For(j,1,n) if(e[i][j])
	{
		if(bel[i]==bel[j]) continue;
		int u=bel[i],v=bel[j];
		ans[i][j]=ct2-(cid[v]-cid[u]);
		if(cid[v]-cid[u]==1&&h[u][v]==1) ans[i][j]++;
//		cout<<i<<" "<<j<<"  "<<cid[u]<<" "<<cid[v]<<"  "<<u<<" "<<v<<"  "<<ans[i][j]<<endl;
	}
	int tct2=ct2;
	For(i,1,tct2) solve(scc[i]);
	
//	puts("ONE");
	int Ans=0;
	For(i,1,n)
	{
		For(j,1,i-1)
		{
			int t=(e[i][j]?ans[i][j]:ans[j][i]);
			Ans=(Ans+pw2[(i-2)*(i-1)/2+j-1]*1ll*t)%P;
//			cout<<j<<" "<<i<<" "<<t<<endl;
		}
	}
	return Ans;
//	For(i,1,n) 
//	{
//		For(j,1,n) putchar(e[i][j]+'0');
//		puts("");
//	}
}
int main()
{
	pw2[0]=1;
	For(i,1,N*N-5) pw2[i]=(pw2[i-1]+pw2[i-1])%P;
	int T=read();
	while(T--) printf("%d\n",work());
	return 0;
}
/*
1
4
1 2
2 3
3 1
4 1
4 2
4 3
*/






Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 128ms
memory: 111248kb

input:

10000
100
1
2
2
8
C0
F0
27
78
AE1
C01
511
D87
EF20
3873
2742
73D0
DC9B0
FB2A3
9C011
9B4E0
95DC00
A7B980
F43531
6A6245
5347BE0
1A6C8A1
88E46D6
64CF3AE
D25F63C1
C894E4C3
1C0AFD73
EC1C3F9A
087CE17C0
22149A380
B28038AF1
B9CA21C7F
D78F5307C1
49045489A2
72C4DE6FD1
7713F40D05
EEE8878EEC1
310E62812B1
DA9D5B...

output:

580750696
13
329192187
3606298
216
0
1983
2
522168599
443783286
595779555
137822
2
827034385
216
6103861
2523
0
982846528
680616979
6140149
97422
126412
5900152
57355800
358646471
64076947
586933507
822948889
66694
807931482
306942208
137822
3228613
85877923
21452420
198
216
219
11549905
523573289
1...

result:

wrong answer 1st numbers differ - expected: '281603732', found: '580750696'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%