QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106360#5307. Subgraph IsomorphismqinsanmaWA 237ms21940kbC++145.5kb2023-05-17 15:18:242023-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;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 21940kb

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: 237ms
memory: 21264kb

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 output format YES or NO expected, but 1617272837384858 found [1085th token]
English 繁體中文 简体中文

Server Time: 2024-12-03 02:41:26 | OpenSource Project