QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#572489#8055. BalancetarjenWA 238ms3928kbC++208.3kb2024-09-18 14:54:482024-09-18 14:54:50

Judging History

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

  • [2024-09-18 14:54:50]
  • 评测
  • 测评结果：WA
  • 用时：238ms
  • 内存：3928kb
查看
  • [2024-09-18 14:54:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const bool test =false;
bool solve(){
    int n,m;cin>>n>>m;
    int bcc_cnt=0;
    auto no = [&](){
        cout<<"No\n";
        return false;
    };
    auto check = [&](vector<int>&ans,vector<int>&color){
        cout<<"Yes\n";
        for(int i=1;i<=n;i++)cout<<ans[color[i]]<<" \n"[i==n];
        return true;
    };
    auto Print_ans = [&](vector<tuple<int,int,int>>&print,vector<int>&color,vector<int>&dfn){
        sort(print.begin(),print.end(),[&](tuple<int,int,int>a,tuple<int,int,int>b){
            return get<1>(a)-get<0>(a)<get<1>(b)-get<0>(b);
        });
        vector<int>ans(bcc_cnt+1);
        set<int>s;
        for(int i=1;i<=bcc_cnt;i++)s.insert(i);
        for(auto [l,r,w]:print){
            // cout<<"l="<<l<<" r="<<r<<" w="<<w<<endl;
            auto it=s.lower_bound(l);
            while(it!=s.end()&&*it<=r){
                ans[dfn[*it]]=w;
                it=s.erase(it);
            }
        }
        return check(ans,color);
    };
    vector<int>col(n+1),a(n+1);
	vector<vector<pair<int,int>>>graph_(n+1);
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        graph_[x].push_back({y,i});
        graph_[y].push_back({x,i});
    }
    vector<vector<int>> ve,have_points;
    vector<int>siz;
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<pair<int,int>> lis;//序列
    vector<int>sum_pre,sum_suf;
    map<int,int> find_pre,find_suf;
    {//init
        vector<int>dfn(n+1),low(n+1);
	    stack<int> stk;
        int dfs_clock=0;
        function<void(int,int,int)> dfs = [&](int u, int fa,int pr){
            dfn[u] = low[u] = ++dfs_clock;
            // cout<<"dfs u = "<<u<<" fa="<<fa<<" clock="<<dfs_clock<<endl;
            stk.push(u);
            for (auto [v,id]:graph_[u])if(id!=pr)
            {
                if (dfn[v])
                {
                    low[u] = min(low[u], dfn[v]);
                }
                else
                {
                    dfs(v, u,id);
                    low[u] = min(low[u], low[v]);
                }
            }
            // cout<<"u="<<u<<" dfn="<<dfn[u]<<" low="<<low[u]<<endl;
            if (low[u] >= dfn[u])
            {
                ++bcc_cnt;
                while (1)
                {
                    int nod = stk.top();
                    stk.pop();
                    col[nod] = bcc_cnt;
                    if (nod == u)
                        break;
                }
            }
        };
        dfs(1,-1,-1);
        ve.resize(bcc_cnt+1);
        have_points.resize(bcc_cnt+1);
        siz.resize(bcc_cnt+1);
        if(test){
            cout<<"color :";for(int i=1;i<=n;i++)cout<<col[i]<<" ";;cout<<endl;
        }
        for(int i=1;i<=n;i++){
            for(auto [it,id]:graph_[i])if(col[i]!=col[it]){
                ve[col[i]].push_back(col[it]);
            }
            siz[col[i]]++;
            have_points[col[i]].push_back(i);
        }
        for(int i=1;i<=bcc_cnt;i++){
            sort(ve[i].begin(),ve[i].end());
            ve[i].resize(unique(ve[i].begin(),ve[i].end())-ve[i].begin());
        }

        map<int,int> ma;
        for(int i=1;i<=n;i++)ma[a[i]]++;
        lis=vector<pair<int,int>>(ma.begin(),ma.end());
        sum_pre.resize(lis.size());
        sum_suf.resize(lis.size());
        for(int i=0;i<lis.size();i++)sum_pre[i]=sum_suf[i]=lis[i].second;
        for(int i=1;i<lis.size();i++)sum_pre[i]+=sum_pre[i-1];
        for(int i=lis.size()-2;i>=0;i--)sum_suf[i]+=sum_suf[i+1];
        for(int i=0;i<lis.size();i++){
            find_pre[sum_pre[i]]=i;
            find_suf[sum_suf[i]]=i;
        }
    }
    vector<int>L(bcc_cnt+1),R(bcc_cnt+1),dfn(bcc_cnt+1);
    vector<int>match_pre(bcc_cnt+1,-1),match_suf(bcc_cnt+1,-1);
    vector<set<pair<int,int>>> s_pre(lis.size()),s_suf(lis.size());
    vector<int>son_siz(bcc_cnt+1);
    if(test){
        cout<<"lis :";
        for(auto [x,y]:lis)cout<<x<<"/"<<y<<" ";;cout<<endl;
        for(auto it:sum_pre)cout<<it<<" ";;cout<<endl;
        for(auto it:sum_suf)cout<<it<<" ";;cout<<endl;
    }
    {//get match
        int cnt=0;
        function<void(int,int)> dfs = [&](int x,int h){
            L[x]=++cnt;
            dfn[cnt]=x;
            son_siz[x]=siz[x];
            for(auto it:ve[x])if(it!=h){
                dfs(it,x);
                son_siz[x]+=son_siz[it];
            }
            R[x]=cnt;
            if(find_pre.find(son_siz[x])!=find_pre.end()){
                int i=find_pre[son_siz[x]];
                if(i==0)match_pre[x]=i;
                else{
                    auto it=s_pre[i-1].lower_bound(make_pair(L[x],0));
                    if(it!=s_pre[i-1].end()){
                        auto [l,r]=*it;
                        if(L[x]<=l&&r<=R[x])match_pre[x]=i;
                    }
                }
            }
            if(find_suf.find(son_siz[x])!=find_suf.end()){
                int i=find_suf[son_siz[x]];
                if(i==lis.size()-1)match_suf[x]=i;
                else{
                    auto it=s_suf[i+1].lower_bound(make_pair(L[x],0));
                    if(it!=s_suf[i+1].end()){
                        auto [l,r]=*it;
                        if(L[x]<=l&&r<=R[x])match_suf[x]=i;
                    }
                }
            }
            if(match_pre[x]!=-1)s_pre[match_pre[x]].insert({L[x],R[x]});
            if(match_suf[x]!=-1)s_suf[match_suf[x]].insert({L[x],R[x]});
        };
        dfs(1,0);
        if(test){
            cout<<"match :\n";
            for(int i=1;i<=bcc_cnt;i++)cout<<match_pre[i]<<" \n"[i==bcc_cnt];
            for(int i=1;i<=bcc_cnt;i++)cout<<match_suf[i]<<" \n"[i==bcc_cnt];
        }
    }
    
    {// get ans
        vector<tuple<int,int,int>> print;
        auto print_pre = [&](int x,int i){
            if(test){
                cout<<"print_pre x="<<x<<" i="<<i<<endl;
            }
            for(int l=L[x],r=R[x];i>=0;i--){
                print.emplace_back(l,r,lis[i].first);
                if(i>0){
                    auto it=s_pre[i-1].lower_bound({l,0});
                    assert(it!=s_pre[i-1].end());
                    auto [L,R]=*it;
                    assert(l<=L&&R<=r);
                    l=L,r=R;
                }
            }
        };
        auto print_suf = [&](int x,int i){
            if(test){
                cout<<"print_suf x="<<x<<" i="<<i<<endl;
            }
            for(int l=L[x],r=R[x];i<(int)lis.size();i++){
                print.emplace_back(l,r,lis[i].first);
                if(i+1<(int)lis.size()){
                    auto it=s_suf[i+1].lower_bound({l,0});
                    assert(it!=s_suf[i+1].end());
                    auto [L,R]=*it;
                    assert(l<=L&&R<=r);
                    l=L,r=R;
                }
            }
        };
        if(match_pre[1]==(int)lis.size()-1){
            print_pre(1,(int)lis.size()-1);
            return Print_ans(print,col,dfn);
        }
        else if(match_suf[1]==0){
            print_suf(1,0);
            return Print_ans(print,col,dfn);
        }
        else {
            for(int i=0;i+2<(int)lis.size();i++){
                for(auto [l,r]:s_pre[i]){
                    auto it=s_suf[i+2].lower_bound({r+1,0});
                    if(it!=s_suf[i+2].end()){

                        print_pre(dfn[l],i);
                        print_suf(dfn[it->first],i+2);
                        print.emplace_back(1,n,i+1);
                        return Print_ans(print,col,dfn);
                    }
                    it=s_suf[i+2].lower_bound({l,0});
                    if(it==s_suf[i+2].begin())continue;
                    it=prev(it);
                    if(it->second>=l){
                        if(it==s_suf[i+2].begin())continue;
                        it=prev(it);
                    }
                    {
                        print_pre(dfn[l],i);
                        print_suf(dfn[it->first],i+2);
                        print.emplace_back(1,n,i+1);
                        return Print_ans(print,col,dfn);
                    }
                }
            }
        }
    }
    return no();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)solve();
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2

output:

Yes
1 2 3 4 5
No
Yes
2 3 1 2 2
Yes
2 2 1 1 1
No

result:

ok ok (5 test cases)

Test #2:

score: 0
Accepted
time: 179ms
memory: 3616kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

output:

Yes
2 2 3 1
No
Yes
1 1 1
No
No
Yes
2 1 1 1
No
No
Yes
1 1
Yes
1 1
Yes
1 1
Yes
1 1 1 1
No
Yes
1 1 1 1 1
Yes
1 3 1 1 1
Yes
1 1 1
Yes
1 2
Yes
1 1 1 1 1
Yes
1 2
No
Yes
1 1
Yes
1 1 1
Yes
1 1
Yes
1 1 1 1
Yes
1 1
Yes
2 2 2 2 2
Yes
1 1 1 1 1
Yes
1 1
Yes
1 1 1 2
No
Yes
1 1
No
Yes
1 1
No
No
No
Yes
1 1 1 1 2
Ye...

result:

ok ok (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 238ms
memory: 3928kb

input:

83335
9 17
1 4
8 9
5 2
1 3
2 7
1 7
2 8
6 7
2 4
1 8
5 8
7 1
8 6
4 6
4 7
6 9
7 9
7 3 4 4 7 4 2 4 8
6 9
3 1
1 2
3 5
1 2
3 4
4 5
6 3
6 1
6 2
4 3 2 2 1 3
9 8
9 3
5 7
5 9
2 6
1 8
4 1
4 2
4 3
4 2 5 3 4 5 4 5 4
6 7
2 1
1 5
6 1
3 1
6 5
2 4
5 3
2 1 2 1 2 1
4 6
2 1
4 2
1 4
1 2
1 4
3 1
2 2 4 2
6 10
2 3
3 5
2 1
...

output:

No
No
Yes
3 4 4 4 5 4 5 2 5
No
Yes
2 2 4 2
No
Yes
3 2 3 3
Yes
2 2 1
No
Yes
1 1 1 1 1
No
Yes
1 1 1
Yes
1 1 3 3 3
Yes
1 1
Yes
1 1
Yes
1 1 1 1
Yes
3 1 3
No
Yes
1 1 1 1 1 1 1 1
Yes
1 1 1 1 1 1 1
No
Yes
1 1
No
Yes
1 1 1 1 1
Yes
2 1 1 2 1
No
Yes
1 2 3 1 3 3 3 1
No
No
No
No
No
No
No
No
No
No
No
No
Yes
7 6 ...

result:

wrong answer 4-th smallest numbers are not same (test case 40)
English 繁體中文 简体中文

Server Time: 2024-12-02 14:49:55 | OpenSource Project