QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#106360	#5307. Subgraph Isomorphism	qinsanma	WA	237ms	21940kb	C++14	5.5kb	2023-05-17 15:18:24	2023-05-17 15:18:28

Judging History

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

[2023-10-15 17:25:08]
管理员手动重测本题所有提交记录

测评结果：WA
用时：139ms
内存：21920kb

查看

[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:18:28]
评测

测评结果：0
用时：237ms
内存：21940kb

查看

[2023-05-17 15:18:24]
提交

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]=1;
    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 nowcnt=0;
    while(t--)
    {


nowcnt++;

        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();

        vector<char>tempfuck;

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

            tempfuck.push_back((char)(x+'0'));
            tempfuck.push_back((char)(y+'0'));

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

        if(nowcnt==1085)
        {
            string debug="";
            for(auto it:tempfuck)
                debug+=it;

            cout<<debug<<endl;
        }

        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: 4ms

memory: 21940kb

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: 237ms

memory: 21264kb

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 output format YES or NO expected, but 1617272837384858 found [1085th token]