QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94286 | #6127. Kawa Exam | installb# | Compile Error | / | / | C++14 | 4.4kb | 2023-04-05 16:54:41 | 2023-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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 | ^~~~~~~~~