QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330675#8055. Balanceucup-team1134#WA 131ms7720kbC++236.7kb2024-02-17 17:42:262024-02-17 17:42:27

Judging History

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

  • [2024-02-17 17:42:27]
  • 评测
  • 测评结果：WA
  • 用时：131ms
  • 内存：7720kb
查看
  • [2024-02-17 17:42:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;


vector<int> G[MAX],bel[MAX];

// https://ei1333.github.io/library/test/verify/yosupo-two-edge-connected-components.test.cpp

template< typename G >
struct LowLink {
  const G &g;
  vector< int > used, ord, low;
  vector< int > articulation;
  vector< pair< int, int > > bridge;

  LowLink(const G &g) : g(g) {}

  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false;
    int cnt = 0;
    bool beet = false;
    for(auto &to : g[idx]) {
      if(to == par) {
        if(!exchange(beet, true)) continue;
      }
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= ~par && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int) to));
      } else {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }

  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }
};

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename GG >
struct TwoEdgeConnectedComponents : LowLink< GG > {
  using LL = LowLink< GG >;
  vector< int > comp;

  TwoEdgeConnectedComponents(const GG &g) : LL(g) {}

  int operator[](const int &k) {
    return comp[k];
  }

  void dfs(int idx, int par, int &k) {
    if(~par && this->ord[par] >= this->low[idx]) comp[idx] = comp[par];
    else comp[idx] = k++;
    for(auto &to : this->g[idx]) {
      if(comp[to] == -1) dfs(to, idx, k);
    }
  }

  void build(UnWeightedGraph &t) {
    LL::build();
    comp.assign(this->g.size(), -1);
    int k = 0;
    for(int i = 0; i < comp.size(); i++) {
      if(comp[i] == -1) dfs(i, -1, k);
    }
    t.resize(k);
    for(auto &e : this->bridge) {
      int x = comp[e.first], y = comp[e.second];
        G[x].push_back(y);
        G[y].push_back(x);
    }
  }
};

vector<int> A,B;

int dp[MAX],siz[MAX];

void make(int u,int p){
    dp[u]=-1;
    siz[u]=si(bel[u]);
    for(int to:G[u]){
        if(to==p) continue;
        
        make(to,u);
        
        siz[u]+=siz[to];
        chmax(dp[u],dp[to]);
    }
    
    if(dp[u]+1<si(A)&&A[dp[u]+1]==siz[u]) dp[u]++;
}

int ans=-1;

void solve(int u,int p){
    vector<pair<int,int>> L,R;
    for(int to:G[u]){
        L.push_back(mp(dp[to],to));
    }
    R=L;
    for(int i=1;i<si(L);i++) chmax(L[i],L[i-1]);
    for(int i=si(R)-2;i>=0;i--) chmax(R[i],R[i+1]);
    
    if(si(L)) dp[u]=L.back().fi;
    else dp[u]=-1;
    if(dp[u]+1<si(A)&&A[dp[u]+1]==siz[u]) dp[u]++;
    
    if(dp[u]==si(A)-1) ans=u;
    
    for(int i=0;i<si(G[u]);i++){
        if(G[u][i]==p) continue;
        int to=G[u][i];
        
        int a=dp[u],b=dp[to];
        int c=siz[u],d=siz[to];
        
        siz[u]-=d;
        siz[to]=c;
        
        int ma=-1;
        if(i) chmax(ma,L[i-1].fi);
        if(i+1<si(R)) chmax(ma,R[i+1].fi);
        
        dp[u]=ma;
        if(dp[u]+1<si(A)&&A[dp[u]+1]==siz[u]) dp[u]++;
        
        solve(to,u);
        
        dp[u]=a;
        dp[to]=b;
        siz[u]=c;
        siz[to]=d;
        
    }
}

int sp[MAX],ANS[MAX];

void mogu(int u,int x){
    for(int to:G[u]){
        if(x&&dp[to]==x-1&&A[x-1]==siz[to]){
            sp[to]=B[x-1];
            mogu(to,x-1);
            return;
        }
    }
    for(int to:G[u]){
        if(x&&dp[to]==x&&siz[to]<siz[u]){
            mogu(to,x);
            return;
        }
    }
}

void hiro(int u){
    for(int x:bel[u]){
        ANS[x]=sp[u];
    }
    for(int to:G[u]){
        if(siz[to]<siz[u]){
            if(sp[to]==-1) sp[to]=sp[u];
            hiro(to);
        }
    }
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;cin>>Q;
    while(Q--){
        int N, M;
        cin >> N >> M;
        UnWeightedGraph g(N);
        for(int i = 0; i < M; i++) {
          int a, b;
            cin >> a >> b;a--;b--;
          g[a].emplace_back(b);
          g[b].emplace_back(a);
        }
        TwoEdgeConnectedComponents< UnWeightedGraph > uku(g);
        UnWeightedGraph t;
        uku.build(t);
        int n=t.size();
        
        for(int i=0;i<N;i++){
            bel[uku[i]].push_back(i);
        }
        
        vector<int> hin(N+1);
        for(int i=0;i<N;i++){
            int x;cin>>x;
            hin[x]++;
        }
        
        vector<pair<int,int>> S;
        for(int i=1;i<=N;i++){
            if(hin[i]) S.push_back(mp(i,hin[i]));
        }
        
        for(int i=0;i<n;i++){
            dp[i]=-1;
            siz[i]=0;
            sp[i]=-1;
        }
        A.clear();
        B.clear();
        for(auto [a,b]:S){
            A.push_back(b);
            B.push_back(a);
        }
        for(int i=1;i<si(A);i++) A[i]+=A[i-1];
        
        ans=-1;
        
        make(0,-1);
        
        solve(0,-1);
        
        if(ans==-1){
            cout<<"No\n";
        }else{
            cout<<"Yes\n";
            make(ans,-1);
            sp[ans]=B[si(B)-1];
            mogu(ans,si(B)-1);
            hiro(ans);
            for(int i=0;i<N;i++){
                if(i) cout<<" ";
                cout<<ANS[i];
            }
            cout<<"\n";
        }
        
        for(int i=0;i<=n;i++){
            G[i].clear();
            bel[i].clear();
        }
    }
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7720kb

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 1 2 2 3
Yes
2 2 1 1 1
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 131ms
memory: 5684kb

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 2 3
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 2 1 1
No
Yes
1 1
No
Yes
1 1
No
No
No
Yes
1 1 2 1 1
Ye...

result:

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

服务器时间: 2024-12-12 00:04:10 | 开源项目