QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120837#6127. Kawa ExampemguimnRE 2ms8248kbC++144.5kb2023-07-07 11:41:222023-07-07 11:41:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 11:41:31]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:8248kb
  • [2023-07-07 11:41:22]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
#define gcd __gcd
#define endl "\n"
#define task "hihi"
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;  
int n, m, a[N], num[N], low[N], timedfs = 0, total = 0, comp[N], freq[N], rfreq[N], ans[N], sz[N], source[N]; vector<pii> adj[N];
vector<int> vert;
bool isBridge[N], vis[N], big[N];
multiset<int> s1, s2;
void reset(){
    total = timedfs = 0;
    for(int i = 1; i <= n; i++){
        adj[i].clear();
        num[i] = low[i] = 0;
        sz[i] = source[i] = 0;
        freq[a[i]] = rfreq[a[i]] = 0;
        comp[i] = 0;
        sz[i] = 0;
        vis[i] = big[i] = false;
    }
    for(int i = 1; i <= m; i++){
        isBridge[i] = false;
        ans[i] = 0;
    }
    vert.clear();
    s1.clear(), s2.clear();
}
void dfs_tree(int i, int pre){
    num[i] = low[i] = ++timedfs;
    sz[i] = 1;
    bool ok = false;
    for(pii e : adj[i]){
        int x = e.first, id = e.second;
        if(x == pre && !ok){    
            ok = true;
            continue;
        }
        if(!num[x]){
            dfs_tree(x, i); sz[i] += sz[x];
            low[i] = min(low[i], low[x]);
            if(low[x] > num[i]){
                isBridge[id] = true;
            }
        } else{
            low[i] = min(low[i], num[x]);
        }
    }
}
void dfs_ans(int i, int pre){
    vert.pb(i);
    vis[i] = true;
    s2.erase(s2.find(rfreq[a[i]]));
    rfreq[a[i]]++; 
    s2.insert(rfreq[a[i]]);
    for(pii e : adj[i]){
        int x = e.first, id = e.second;
        if(!vis[x]){
            dfs_ans(x, i);
        }  
    }   
    comp[i] = *s2.rbegin();
}
void add(int i, int pre){
    s1.erase(s1.find(freq[a[i]]));
    s2.erase(s2.find(rfreq[a[i]]));
    freq[a[i]]++;
    rfreq[a[i]]--;
    s2.insert(rfreq[a[i]]);
    s1.insert(freq[a[i]]);
    for(pii e : adj[i]){
        int x = e.first, id = e.second;
        if(x == pre || big[x] || num[x] > num[i]) continue;
        add(x, i);
    }
}
void rem(int i, int pre){
    s1.erase(s1.find(freq[a[i]]));
    s2.erase(s2.find(rfreq[a[i]]));
    freq[a[i]]--;
    rfreq[a[i]]++;
    s2.insert(rfreq[a[i]]);
    s1.insert(freq[a[i]]);
    for(pii e : adj[i]){
        int x = e.first, id = e.second;
        if(x == pre || big[x] || num[x] > num[i]) continue;
        rem(x, i);
    }
}
void dfs_final(int i, int pre, int root, int hehe, bool keep){
    source[i] = root;
    int h_sz = -1, h_child = -1, h_id = 0;
    for(pii e : adj[i]){
        int x = e.first, id = e.second;
        if(x == pre) continue;
        if(num[x] < num[i]) continue;
        if(h_sz < sz[x]){
            h_sz = sz[x], h_child = x, h_id = id;
        }
    }
    for(pii e : adj[i]){
        int x = e.first, id = e.second;
        if(x == pre || x == h_child) continue;
        if(num[x] > num[i] && isBridge[id]){
            dfs_final(x, i, i, id, 0);
        }     }
    if(h_child != -1) {
        dfs_final(h_child, i, i, h_id, 1); big[h_child] = true;
    }
    add(i, pre);
    if(isBridge[hehe]) ans[hehe] = *s1.rbegin() + *s2.rbegin();
    if(h_child != -1) big[h_child] = false;
    if(keep == 0){
        rem(i, pre);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    int t; cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= m; i++){
            int x, y; cin >> x >> y;
            adj[x].pb({y, i});
            adj[y].pb({x, i});
        }
        for(int i = 1; i <= n; i++) {
            if(!num[i]) dfs_tree(i, i);
        }
        for(int i = 1; i <= n; i++) s2.insert(0);
        for(int i = 1; i <= n; i++) s1.insert(0);

        fill(vis + 1, vis + n + 1, false);
        for(int i = 1; i <= n; i++){
            if(!vis[i]){
                dfs_ans(i, i); 
                dfs_final(i, i, i, 0, 0);
                total += comp[i];
                for(int x : vert) rfreq[a[x]] = freq[a[x]] = 0;
                vert.clear();
                while(*s1.rbegin()) s1.erase(s1.find(*s1.rbegin())), s1.insert(0);
                while(*s2.rbegin()) s2.erase(s2.find(*s2.rbegin())), s1.insert(0);
            }
        }
        for(int i = 1; i <= m; i++){
            if(isBridge[i]) cout << total - comp[source[i]] + ans[i]; 
            else cout << total;
            if(i < m) cout << " ";      
        }
        cout << endl;
        reset();
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3
7 5
1 2 1 2 1 2 1
1 2
1 3
2 4
5 6
5 7
3 3
1 2 3
1 2
1 3
2 3
2 3
12345 54321
1 2
1 2
1 1

output:

6 5 5 5 4
1 1 1
1 1 1

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

5557
2 7
79960 79960
2 2
1 1
1 1
2 2
1 1
2 1
1 2
9 8
21881 70740 70740 21881 22458 22458 639 21881 70740
3 3
1 6
5 8
7 5
5 7
2 3
5 1
7 6
6 7
13064 20716 6746 13064 6746 69225
5 5
4 1
4 1
1 6
4 5
3 2
3 2
8 4
45146 14400 45146 45146 14400 72969 14400 45146
8 6
1 3
4 6
8 3
18 13
48132 37949 92338 92338...

output:


result: