QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#182865 | #5407. 基础图论练习题 | FLY | 0 | 128ms | 111248kb | C++14 | 4.9kb | 2023-09-18 17:36:02 | 2023-09-18 17:36:02 |
Judging History
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%