Submission #8447

#	Time	Username	Problem	Language	Result	Execution time	Memory
8447		adream	비용 (KOI11_cost)	C++98	22.80 / 24	60 ms	11500 KiB

cost

#include <cstdio>
#include <algorithm>
#include <vector>
#define BIG 1000000000
 
using namespace std;
 
int n, m, lastgraphindex;
long long int sumCost, pastCost;
long long int ans;
int graphindex[100010];
 
class edge
{
    public:
        int u, v, cost;
        bool operator > ( const edge & ed) const
         {
                 if( cost > ed.cost) return true;
                 else if(cost == ed.cost) return u>ed.u;
                 return false;
         }
        bool operator < ( const edge & ed) const
         {
                 if( cost < ed.cost) return true;
                 else if(cost == ed.cost) return u<ed.u;
                 return false;
         }
 
};
 
vector<edge> container;
vector<int> graph[100010];
 
void ini()
{
    fill(&graphindex[0],&graphindex[100010],-1);
}
 
void input()
{
    edge temp;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&temp.u,&temp.v,&temp.cost);
        sumCost+=temp.cost;
        container.push_back(temp);
    }
}
 
void process()
{
    edge now;
    vector<edge>::iterator it=container.end();
    sort(container.begin(),container.end());
    while(true)
    {
        it--;
        now = *it;
        if(graphindex[now.u]==-1 && graphindex[now.v]==-1)
        {
            graphindex[now.u] = graphindex[now.v] = lastgraphindex;
            graph[lastgraphindex].push_back(now.u);
            graph[lastgraphindex].push_back(now.v);
            ans+= (sumCost - pastCost);
            lastgraphindex++;
            pastCost+=now.cost;
        }
        else if(graphindex[now.u]!=graphindex[now.v])
        {
            if(graphindex[now.u]==-1 || graphindex[now.v]==-1)
            {
                if(graphindex[now.u]==-1)
                {
                    int temp=now.u;
                    now.u=now.v, now.v= temp;
                }
                ans += graph[graphindex[now.u]].size() * (sumCost - pastCost);
                graphindex[now.v] = graphindex[now.u];
                graph[graphindex[now.u]].push_back(now.v);
                pastCost+=now.cost;
            }
            else
            {
                ans +=  graph[graphindex[now.v]].size() * graph[graphindex[now.u]].size() * (sumCost - pastCost);
                int newindex = min(graphindex[now.v],graphindex[now.u]);
                if(newindex!=graphindex[now.v])
                {
                    vector<int>::iterator it2;
                    int tempindex = graphindex[now.v];
                    for(it2 = graph[tempindex].begin(); it2!=graph[tempindex].end();++it2)
                    {
                        graph[newindex].push_back(*it2);
                        graphindex[*it2]=newindex;
                    }
                }
                else
                {
                    vector<int>::iterator it3;
                    int tempindex = graphindex[now.u];
                    for(it3 = graph[tempindex].begin(); it3!=graph[tempindex].end();++it3)
                    {
                        graph[newindex].push_back(*it3);
                        graphindex[*it3]=newindex;
                    }
                }
 
                pastCost+=now.cost;        
            }
        }
        else
        {
            pastCost+=now.cost;
        }
        if(ans>=BIG) ans%=BIG;
        if(it==container.begin()) break;
    }
}
 
int main()
{
    input();
    ini();
    process();
    printf("%lld",ans%BIG);
 
}

• Subtask 1: 3.6 / 4.8
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12