CODE FESTIVAL 2016 Final

Submission #1108796

Source codeソースコード

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fin "\n"

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
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);}

typedef tuple<LL,int,int> T;
typedef pair<int,int> P;

#define fi first
#define se second
int N,Q;
map<int,int> rg;
priority_queue<T,vector<T>,greater<T>> que;
T abc[212345];
int used[212345];
bool in_range(LL a){
    auto nxt=rg.lower_bound(a);
    return (nxt!=rg.end()&&nxt->se<=a);
}
int  add_range(LL a){
    if(in_range(a))return 0;
    auto nxt=rg.lower_bound(a);
    if(nxt!=rg.end()&&nxt->se==a+1){
        //a-1] a [a+1
        if(rg.count(a-1)==1){
            int bg=rg[a-1];
            int ed=nxt->fi;
            rg.erase(a-1);
            rg[ed]=bg;
        }
        //null a [a+1
        else{
            int bg=a;
            int ed=nxt->fi;
            rg[ed]=bg;
        }
    }
    else{
        //a-1] a null
        if(rg.count(a-1)==1){
            int bg=rg[a-1];
            int ed=a;
            rg.erase(a-1);
            rg[ed]=bg;
        }
        //null a null
        else{
            int bg=a;
            int ed=a;
            rg[ed]=bg;
        } 
    }
    return 1;
}
LL get_nxt(int &a,int &b){
    LL prev_a=a;
    LL prev_b=b;
    LL na=rg.lower_bound(a)->fi+1;
    LL nb=rg.lower_bound(b)->fi+1;
    LL cost;
    if(na-a>=nb-b){
        na=a+(nb-b-1);
        cost=na-a+nb-b;
        b=na%N;
        a=nb%N;
    }
    else{
        nb=b+(na-a);
        cost=na-a+nb-b;
        b=nb%N;
        a=na%N;
    }
    return cost;
}

int main(){
    scanf("%d %d",&N,&Q);
    vector<vector<int>> g(N);
    int rest=N;
    LL res=0;
    REP(i,Q){
        int a,b;LL c;
        scanf("%d %d %lld",&b,&a,&c);
        if(a==b){
            int tmp=a;
            a=(b+1)%N,c++;b=tmp;
        }
        abc[i]=T(c,a,b);
        g[a].push_back(i);
        g[b].push_back(i);
    }
    REP(i,Q)used[i]=0;
    //init
    {
        int id=0;
        REP(i,Q)
            if(abc[i]<abc[id])
                id=i;
        int a,b;LL c;
        tie(c,a,b)=abc[id];
        rest-=add_range(a);add_range(a+N);
        rest-=add_range(b);add_range(b+N);
        res+=c;
        
        while(g[a].size()){
            if(!used[g[a].back()]){
                que.push(abc[g[a].back()]);
            }
            used[g[a].back()]=1;
            g[a].pop_back();
        }
        while(g[b].size()){
            if(!used[g[b].back()]){
                que.push(abc[g[b].back()]);
            }
            used[g[b].back()]=1;
            g[b].pop_back();
        }
    }
    while(rest){
        auto top=que.top();que.pop();
        int a,b;LL c;

        tie(c,a,b)=top;
        //cout<<a<<" "<<b<<" "<<c<<endl;
        if(!in_range(a)){
            // cout<<a<<" "<<b<<" "<<c<<endl;
            res+=c;
            rest-=add_range(a);add_range(a+N);
            while(g[a].size()){
                if(!used[g[a].back()]){
                    que.push(abc[g[a].back()]);
                }
                used[g[a].back()]=1;
                g[a].pop_back();
            }
        }
        else if(!in_range(b)){
            //cout<<a<<" "<<b<<" "<<c<<endl;
            res+=c;
            rest-=add_range(b);add_range(b+N);
            while(g[b].size()){
                if(!used[g[b].back()]){
                    que.push(abc[g[b].back()]);
                }
                used[g[b].back()]=1;
                g[b].pop_back();
            }

        }
        c+=get_nxt(a,b);
        que.push(T(c,a,b));
    }

    
    
    cout<<res<<endl;

    return 0;
}

Submission

Task問題 G - Zigzag MST
User nameユーザ名 btk
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 3854 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&Q);
^
./Main.cpp:93:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&b,&a,&c);
^

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 0 / 1300 sample-01.txt,sample-02.txt,sample-03.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 3 ms 256 KB
01-02.txt AC 74 ms 9896 KB
01-03.txt WA
01-04.txt AC 51 ms 4992 KB
01-05.txt AC 48 ms 4992 KB
01-06.txt AC 55 ms 4992 KB
01-07.txt WA
01-08.txt WA
01-09.txt WA
01-10.txt WA
01-11.txt WA
01-12.txt WA
01-13.txt WA
01-14.txt WA
01-15.txt WA
01-16.txt WA
01-17.txt WA
01-18.txt TLE
01-19.txt WA
01-20.txt WA
01-21.txt WA
01-22.txt WA
01-23.txt WA
01-24.txt TLE
01-25.txt TLE
01-26.txt AC 58 ms 4992 KB
01-27.txt WA
01-28.txt WA
01-29.txt WA
01-30.txt WA
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 2 ms 256 KB
sample-03.txt AC 2 ms 256 KB