CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1127570

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

struct cww{cww(){
    ios::sync_with_stdio(false);cin.tie(0);
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}

namespace _DSU{
    int cnt=0;
    int mem[2][212345];
    int* get(){
        return mem[cnt++];
    }
}
LL res[112345];
int S[112345];
int T[112345];
set<int> query[41234];
int task[112345];
class UnionFind{
private:
    int *par,*rank;
    int find(int x){
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
public:
    UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
        for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
    }
    UnionFind(int n):UnionFind(n,_DSU::get(),_DSU::get()){}
    int unite(int x, int y){
        x = find(x);y = find(y);
        if (x == y)return -1;
        int sz=0;
        if(query[x].size()>query[y].size())swap(x,y);
        for(auto &it:query[x]){
            if(query[y].count(it)){
                task[sz++]=it;
                query[y].erase(it);
            }
            else query[y].insert(it);
        }
        query[x].clear();
        if (rank[x] < rank[y])swap(x,y);
        if(query[x].size()==0)swap(query[x],query[y]);
        par[y] = x;
        if (rank[x] == rank[y])rank[x]++;
        return sz;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};
typedef tuple<LL,int,int> E;
int main(){
    int N,M,Q;
    cin>>N>>M;
    vector<E> e(M);
    REP(i,M){
        int s,t;LL c;
        cin>>s>>t>>c;
        e[i]=E(c,s,t);
    }
    sort(e.begin(),e.end());
    
    cin>>Q;
    REP(i,Q){
        cin>>S[i]>>T[i];
        query[S[i]].insert(i);
        query[T[i]].insert(i);
    }
    LL cost=0;
    UnionFind uf(N+1);
    REP(i,M){
        int a,b;LL c;
        tie(c,a,b)=(e[i]);
        int k=uf.unite(a,b);
        if(k==-1)continue;
        REP(i,k){
            res[task[i]]=c;
        }
        cost+=c;
    }
    REP(i,Q)cout<<cost-res[i]<<fin;
    
    return 0;
}

Submission

Task問題 A - グラフ / Graph
User nameユーザ名 btk
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 2453 Byte
File nameファイル名
Exec time実行時間 346 ms
Memory usageメモリ使用量 21120 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt
subtask1 200 / 200 sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 300 / 300 sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt
All 200 / 200 sample_1.txt,sample_2.txt,sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 2 ms 3968 KB
sample_2.txt AC 3 ms 3968 KB
subtask_1_1.txt AC 3 ms 4096 KB
subtask_1_10.txt AC 68 ms 7040 KB
subtask_1_11.txt AC 3 ms 3968 KB
subtask_1_2.txt AC 16 ms 4608 KB
subtask_1_3.txt AC 135 ms 10240 KB
subtask_1_4.txt AC 4 ms 3968 KB
subtask_1_5.txt AC 4 ms 4096 KB
subtask_1_6.txt AC 35 ms 5504 KB
subtask_1_7.txt AC 135 ms 10240 KB
subtask_1_8.txt AC 4 ms 3968 KB
subtask_1_9.txt AC 6 ms 4096 KB
subtask_2_1.txt AC 138 ms 10496 KB
subtask_2_2.txt AC 138 ms 10496 KB
subtask_2_3.txt AC 138 ms 10496 KB
subtask_2_4.txt AC 140 ms 10496 KB
subtask_2_5.txt AC 7 ms 4352 KB
subtask_2_6.txt AC 12 ms 4608 KB
subtask_2_7.txt AC 39 ms 5888 KB
subtask_2_8.txt AC 144 ms 10496 KB
subtask_3_1.txt AC 346 ms 20992 KB
subtask_3_2.txt AC 330 ms 21120 KB
subtask_3_3.txt AC 269 ms 14976 KB
subtask_3_4.txt AC 196 ms 14848 KB
subtask_3_5.txt AC 261 ms 17792 KB
subtask_3_6.txt AC 328 ms 19456 KB
subtask_3_7.txt AC 345 ms 20992 KB
subtask_3_8.txt AC 345 ms 20864 KB