QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106354#5307. Subgraph IsomorphismqinsanmaWA 188ms22864kbC++145.2kb2023-05-17 15:14:142023-05-17 15:14:18

Judging History

你现在查看的是测评时间为 2023-05-17 15:14:18 的历史记录

  • [2023-10-15 17:25:07]
  • 管理员手动重测本题所有提交记录
  • 测评结果：WA
  • 用时：120ms
  • 内存：22520kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 15:14:18]
  • 评测
  • 测评结果：0
  • 用时：188ms
  • 内存：22864kb
查看
  • [2023-05-17 15:14:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef unsigned long long  ull;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
typedef pair<ull,ull> HASH ;

vector<int>v[500000+10];
int du[500000+10],vis[500000+10];
queue<int>q;
int nowzhong[2],nown,fuck;
int sizeson[500000+10],maxx[500000+10];
void getzhong(int now,int pre)
{
    for(auto it:v[now])
    {

        if(it==pre)
            continue;
        if(it==fuck||vis[it]==1)
        {
            getzhong(it,now);
            maxx[now]=max(maxx[now],sizeson[it]);
        }
    }
    maxx[now]=max(maxx[now],nown-sizeson[now]);

   // cout<<maxx[now]<<" ---- "<<endl;
    if(maxx[now]<=nown/2)
    {
        if(nowzhong[0]==0)
        {
            nowzhong[0]=now;
        }
        else
        {
            nowzhong[1]=now;
        }
    }
}

void dfs(int now,int pre)
{
    sizeson[now]++;
    for(auto it:v[now])
    {
        if(it==pre)
            continue;
        if(it==fuck||vis[it]==1)
        {
            dfs(it,now);
            sizeson[now]+=sizeson[it];
        }
    }
}
ull shift(ull x)
{
    x^=mask;
    x^=x<<13;
    x^=x>>7;
    x^=x<<17;
    x^=mask;
    return x;
}

ull gethash(int now,int pre)
{
    //  cout<<now<<endl;
    ull nowhash=1;

    for(auto it:v[now])
    {
        if(it==pre)
            continue;
        if(it==fuck||(vis[it]==1))
        {
            nowhash+=shift(gethash(it,now));
        }
    }
    return nowhash;
}

vector<HASH>ans;
void work(int root)
{

    //cout<<"work" <<" "<<root<<endl;
    fuck=root;
    dfs(root,0);
    //  cout<<"dfs";
    nown=sizeson[root];


    nowzhong[0]=nowzhong[1]=0;

    getzhong(root,0);
    // cout<<"getzhong";
    // cout<<nowzhong[0]<<" "<<nowzhong[1]<<" === "<<endl;
    HASH temp;
    temp.first=gethash(nowzhong[0],0);

    // cout<<temp.first<<endl;
    if(nowzhong[1])
    {
        temp.second=gethash(nowzhong[1],0);
        if(temp.first<temp.second)
            swap(temp.first,temp.second);
    }
    else
        temp.second=temp.first;

    ans.push_back(temp);

}
int main()
{
    //先求树的重心

    int t;
    cin>>t;
//5 5

/*

1 4
1 5
2 5
3 5
4 5


*/
    int fuckcnt=0;
    while(t--)
    {




        int n,m;
        cin>>n>>m;


        for(int i=1; i<=n; i++)
        {
            v[i].clear();
            du[i]=0;
            vis[i]=0;
            sizeson[i]=0;
            maxx[i]=0;
        }

        ans.clear();

        while(!q.empty())
            q.pop();


        for(int i=1; i<=m; i++)
        {
            int x,y;
            cin>>x>>y;


            v[x].push_back(y);
            v[y].push_back(x);
            du[x]++;
            du[y]++;
        }


        if(m==n-1)
        {
            cout<<"YES"<<endl;

        }
        else if(m>n)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            //必有环
            for(int i=1; i<=n; i++)
            {
                if(du[i]==1)
                {
                    q.push(i);
                    vis[i]=1;
                }
            }

            int cnt=n;
            while(!q.empty())
            {
                int now=q.front();
                q.pop();
                vis[now]=1;
                cnt--;

                for(auto it:v[now])
                {
                    du[it]--;
                    if(du[it]==1)
                        q.push(it);
                }
            }



            int root=0;

            for(int i=1; i<=n; i++)
            {
                if(vis[i]==0)
                {
                    root=i;
                    vis[root]=2;
                    break;
                }
            }
            //  cout<<cnt<<endl;

            for(int i=1; i<=cnt; i++)
            {

               // cout<<root<<" ";

                // cout<<i<<endl;
                work(root);

                for(auto it:v[root])
                {
                    if(vis[it]==0)
                    {
                        root=it;
                        vis[it]=2;
                        break;
                    }
                }

            }

            HASH pre=ans[0];
            int flag=0;

            for(auto it:ans)
            {
                if(it!=pre)
                {
                    flag=1;
                }

                //cout<<it.first<<" "<<it.second<<endl;
            }
            if(!flag)
            {
                cout<<"YES"<<endl;

            }
            else
            {

                flag=0;
                for(int i=0; i<ans.size(); i++)
                {
                    if(ans[(i+2)%(int)(ans.size())]!=ans[i])
                    {
                        flag=1;
                    }
                }

                if(flag)
                {
                    cout<<"NO"<<endl;
                }
                else
                {
                    cout<<"YES"<<endl;
                }
            }


        }

    }

    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 22864kb

input:

4
7 6
1 2
2 3
3 4
4 5
5 6
3 7
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 1
1 5
1 0

output:

YES
YES
NO
YES

result:

ok 4 token(s): yes count is 3, no count is 1

Test #2:

score: -100
Wrong Answer
time: 188ms
memory: 21480kb

input:

33192
2 1
1 2
3 2
1 3
2 3
3 3
1 2
1 3
2 3
4 3
1 4
2 4
3 4
4 3
1 3
1 4
2 4
4 4
1 3
1 4
2 4
3 4
4 4
1 3
1 4
2 3
2 4
4 5
1 3
1 4
2 3
2 4
3 4
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 4
1 5
2 5
3 5
4 5
5 4
1 4
1 5
2 5
3 5
5 5
1 4
1 5
2 5
3 5
4 5
5 5
1 4
1 5
2 4
3 5
4 5
5 5
1 4
1 5
2 4
2 5
3 5
5 6
1 4
1 5
2 4
2 5
3 ...

output:

YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

wrong answer expected NO, found YES [1085th token]
English 繁體中文 简体中文

Server Time: 2024-12-03 02:44:46 | OpenSource Project