QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94286#6127. Kawa Examinstallb#Compile Error//C++144.4kb2023-04-05 16:54:412023-04-05 16:54:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 16:54:44]
  • 评测
  • [2023-04-05 16:54:41]
  • 提交

answer

#include <bits/stdc++.h>
#define lson (x << 1)
#define rson ((x << 1) | 1)
using namespace std;
typedef long long ll;
const int N = 400005;

int eu[N],ev[N];

struct segtree{
    int val[N << 2];
    void build(int x,int l,int r){
        if(l == r){
            val[x] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson,l,mid);
        build(rson,mid + 1,r);
        pushup(x);
    }
    void pushup(int x){
        val[x] = max(val[lson],val[rson]);
    }
    void modify(int x,int l,int r,int pos,int v){
        if(l == r){
            val[x] += v;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) modify(lson,l,mid,pos,v);
        if(pos > mid) modify(rson,mid + 1,r,pos,v);
        pushup(x);
    }
    int query(){ return val[1]; }
}tin,tout;

int ec,to[N << 1],nxt[N << 1],hed[N];
int bri[N << 1];
void add_edge(int f,int t){
    ++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec; bri[ec] = 0;
}

int dfn[N],low[N],dfc,a[N];
int mx,cnt[N];
vector <int> ine,inv;

void tarjan(int u,int fe){
    dfn[u] = low[u] = ++ dfc;
    cnt[a[u]] ++; mx = max(mx,cnt[a[u]]);
    inv.push_back(u);
    for(int v,i = hed[u];i;i = nxt[i]){
        v = to[i];
        if(!dfn[v]){
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]) bri[i] = bri[i ^ 1] = 1;
        }
        else if(i != (fe ^ 1)) low[u] = min(low[u],dfn[v]);
    }
}

int col[N];
vector <int> vec[N];
vector <pair <int,int> > G[N];

void dfs_dcc(int u,int id){
    col[u] = id;
    vec[id].push_back(u);
    for(int v,i = hed[u];i;i = nxt[i]){
        v = to[i];
        if(bri[i] || col[v]) continue;
        dfs_dcc(v,id);
    }
}

int son[N],siz[N],L[N],R[N],ln[N],lnc = 0,c,n,m;
int ans[N];

void init_dfs(int u,int f,int fe){
    siz[u] = vec[u].size();
    son[u] = 0;
    ln[++ lnc] = u;
    L[u] = lnc;
    for(auto [v,e] : G[u]){
        if(v == f) continue;
        init_dfs(v,u,e);
        siz[u] += siz[v];
        if(!son[u] || siz[v] > siz[son[u]]) son[u] = v;
    }
    R[u] = lnc;
    ine.push_back(fe); inv.push_back(u);
}

void Add_Point(int x,int v){
    for(int u : vec[x]){
        tin.modify(1,1,n,a[u],v);
        tout.modify(1,1,n,a[u],-v);
    }
}
void Add_Tree(int u,int v){ for(int i = L[u];i <= R[u];i ++) Add_Point(ln[i],v); }
int query(){ return tin.query() + tout.query(); }

void dsu(int u,int f,int fe){
    for(auto [v,e] : G[u]){
        if(v == f || v == son[u]) continue;
        dsu(v,u,e);
        Add_Tree(v,-1);
    }
    for(auto [v,e] : G[u]){
        if(v == son[u]) dsu(v,u,e);
    }
    for(auto [v,e] : G[u]){
        if(v == f || v == son[u]) continue;
        Add_Tree(v,1);
    }
    Add_Point(u,1);
    ans[fe] = query();
}

void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    ec = 1; dfc = 0; lnc = 0;
    for(int i = 1;i <= n;i ++) hed[i] = dfn[i] = col[i] = 0;
    for(int i = 1;i <= m;i ++){
        cin >> eu[i] >> ev[i];
        add_edge(eu[i],ev[i]); add_edge(ev[i],eu[i]);
    }
    int S = 0; mx = 0;
    for(int i = 1;i <= n;i ++){
        if(!dfn[i]){
            tarjan(i,0);
            S += mx;
            for(int u : inv) cnt[a[u]] --;
            inv.clear();
        }
    }
    c = 0;
    for(int i = 1;i <= n;i ++){
        if(col[i]) continue;
        c ++; vec[c].clear(); G[c].clear(); siz[c] = 0;
        dfs_dcc(i,c);
    }
    for(int i = 1;i <= m;i ++){
        if(col[eu[i]] != col[ev[i]]){
            G[eu[i]].push_back(make_pair(ev[i],i));
            G[ev[i]].push_back(make_pair(eu[i],i));
        }
    }
    for(int i = 1;i <= c;i ++){
        if(!siz[i]){
            tin.build(1,1,n);
            tout.build(1,1,n);
            init_dfs(i,0,0);
            for(int u : inv){
                for(int u2 : vec[u]){
                    tin.modify(1,1,n,u2,1);
                }
            }
            dsu(i,0,0);
            cout << i << ' ' << ans[0] << endl;
            for(int u : ine) if(u) ans[u] -= ans[0];
            ine.clear(); inv.clear();
        }
    }
    for(int i = 1;i <= m;i ++){
        if(col[eu[i]] == col[ev[i]]) cout << S << ' ';
        else cout << S + ans[i] << ' ';
    }
    cout << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        solve();
    }
    return 0;
}
sdfsdfsdf

详细

answer.code: In function ‘void init_dfs(int, int, int)’:
answer.code:85:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   85 |     for(auto [v,e] : G[u]){
      |              ^
answer.code: In function ‘void dsu(int, int, int)’:
answer.code:105:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  105 |     for(auto [v,e] : G[u]){
      |              ^
answer.code:110:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  110 |     for(auto [v,e] : G[u]){
      |              ^
answer.code:113:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  113 |     for(auto [v,e] : G[u]){
      |              ^
answer.code: At global scope:
answer.code:183:1: error: ‘sdfsdfsdf’ does not name a type
  183 | sdfsdfsdf
      | ^~~~~~~~~