QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#106354	#5307. Subgraph Isomorphism	qinsanma	WA	188ms	22864kb	C++14	5.2kb	2023-05-17 15:14:14	2023-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;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 22864kb

input:

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:

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]