社区讨论

70pts 求调 WA on #10#13#15#17#18#19

DDeepsick
P14980[USACO26JAN1] COW Traversals G参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mln4kkyt
此快照首次捕获于
2026/02/15 10:27
4 天前
此快照最后确认于
2026/02/19 11:00
1 小时前
查看原帖
方法和题解差不多。bcj[i][0] 表示第 i 头牛在并查集中的父节点。bcj[i][1] 表示以 i 为根的并查集大小。bcj[i][2] 表示以 i 为根的并查集聚会类型，如果没有聚会则为 -1。b[i] 表示第 i 头牛举办聚会的所有日期（从小到大）。a c t 含义与题面中相同（其中 0 表示 C 类聚会，1 表示 O 类，2 表示 W 类）。ans[i][j] 表示第 i 天晚上参加 j 类聚会的牛的数量。
代码：
CPP
#include <iostream>
#include <stack>
using namespace std;
int a[200001],c[200001],t[200001],bcj[200001][3],ans[200001][3];
stack<int> b[200001];
int get(int i) {return bcj[i][0]==i?i:bcj[i][0]=get(bcj[i][0]);}
int main() {
    int n,m,i,j,k;
    char ch;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(i=1;i<=m;i++) {
        cin>>c[i]>>ch;
        b[c[i]].push(i);
        if(ch=='C') t[i]=0;else if(ch=='O') t[i]=1;else t[i]=2;
    }
    for(i=1;i<=n;i++) {bcj[i][0]=i;bcj[i][1]=1;}
    for(i=1;i<=n;i++) if(b[i].empty()) {
        j=get(a[i]);
        if(j!=i) bcj[bcj[i][0]=j][1]+=bcj[i][1];
    }
    for(i=1;i<=n;i++) if(!b[i].empty()) ans[m][bcj[i][2]=t[b[i].top()]]+=bcj[i][1];
    for(i=m;i>1;i--) {
        for(j=0;j<3;j++) ans[i-1][j]=ans[i][j];
        j=c[i];
        ans[i-1][t[i]]-=bcj[j][1];
        b[j].pop();
        if(b[j].empty()) {
            k=get(a[j]);
            if(k==j) bcj[j][2]=-1;
            else {
                bcj[j][0]=k;bcj[k][1]+=bcj[j][1];
                if(bcj[k][2]!=-1) ans[i-1][bcj[k][2]]+=bcj[j][1];
            }
        }
        else ans[i-1][bcj[j][2]=t[b[j].top()]]+=bcj[j][1];
    }
    for(i=1;i<=m;i++) cout<<ans[i][0]<<' '<<ans[i][1]<<' '<<ans[i][2]<<'\n';
    return 0;
}

回复

共 4 条回复，欢迎继续交流。

正在加载回复...