QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106354#5307. Subgraph IsomorphismqinsanmaWA 120ms22520kbC++145.2kb2023-05-17 15:14:142023-10-15 17:25:07

Judging History

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

  • [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: 0ms
memory: 22120kb

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: 120ms
memory: 22520kb

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-02 22:38:32 | OpenSource Project