QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287407#5407. 基础图论练习题Coffins0 7ms6104kbC++142.4kb2023-12-20 15:16:532023-12-20 15:16:53

Judging History

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

  • [2023-12-20 15:16:53]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:6104kb
  • [2023-12-20 15:16:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
using ll=long long;
const int p=1e9+7;
int n;
int edge[N][N];
int deg[N];
int l_hash(char ch)
{
    if('0'<=ch&&ch<='9')
    {
        return ch-'0';
    }
    return ch-'A'+10;
}
int id[N],pos[N],val[N],vl[N],vr[N],sum[N];
int pre[N][3];
bool cmp(int x,int y)
{
    return deg[x]<deg[y];
}
int calc(int l,int r,int typ)
{
    int ans=pre[l-1][0]+(pre[n][0]-pre[r-1][0]);
    if(~typ)
    {
        ans+=pre[r-1][2]-pre[l-1][2];
    }
    else
    {
        ans+=pre[r-1][1]-pre[l-1][1];
    }
    return ans;
}
ll ans=0,bas;
int Calc(int u,int v)
{
    u=pos[u];
    v=pos[v];
    if(val[u]+1==val[v])
    {
        return pre[n][0];
    }
    if(vr[u]>=vl[v])
    {
        return calc(vl[v],vr[u],-1);
    }
    else
    {
        return calc(vr[u],vl[v],1);
    }
}
void solve()
{
    cin>>n;
    fill(deg+1,deg+n+1,0);
    for(int i=1;i<=n-1;i++)
    {
        string s;
        cin>>s;
        for(int j=1,k=0;j<=i;j+=4,k++)
        {
            edge[i+1][j]=l_hash(s[k])&1;
            edge[i+1][j+1]=l_hash(s[k])&2;
            edge[i+1][j+2]=l_hash(s[k])&4;
            edge[i+1][j+3]=l_hash(s[k])&8;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            if(edge[i][j])
            {
                ++deg[i];
            }
            else
            {
                ++deg[j];
            }
        }
    }
    iota(id+1,id+n+1,1);
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        val[i]=deg[id[i]];
        sum[i]=sum[i-1]+val[i];
        pos[id[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]-=i*(i-1)/2;
        vl[i]=(i==1||(vl[i]^vl[i-1]))?i:vl[i-1];
    }
    for(int i=n;i>=1;i--)
    {
        vr[i]=(i==n||(vr[i]^vr[i+1]))?i:vr[i+1];
    }
    for(int i=1;i<=n;i++)
    {
        pre[i][0]=pre[i-1][0]+(sum[i]==0);
        pre[i][1]=pre[i-1][1]+(sum[i]==1);
        pre[i][2]=pre[i-1][2]+(sum[i]==-1);
    }
    ans=0,bas=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            ll res=(edge[i][j])?Calc(j,i):Calc(i,j);
            ans=(ans+res*bas%p)%p;
            bas=(bas<<1)%p;
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 6104kb

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:

281603732
13
285212672
371842543
81
0
1983
2
268503039
268435455
719476515
32785
2
719476771
111
2621567
2513
0
719476275
371842543
2097159
41087
34815
3113984
719478307
502774846
719476267
719476259
719476259
65128
268697611
719477283
36863
2162815
719476259
371842543
104
67
151
4720639
268435455
1...

result:

wrong answer 5th numbers differ - expected: '84', found: '81'

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%