oj.uz

Submission #8447

# Submission time Handle Problem Language Result Execution time Memory
8447 2014-09-14T12:14:29 Z adream 비용 (KOI11_cost) C++
22.8 / 24
 60 ms 11500 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3944 KB Output is correct
2 Runtime error 0 ms 3940 KB SIGSEGV Segmentation fault
3 Correct 0 ms 3944 KB Output is correct
4 Correct 0 ms 3944 KB Output is correct

Subtask #2
7.2 / 7.2

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3944 KB Output is correct
2 Correct 0 ms 3944 KB Output is correct
3 Correct 0 ms 3944 KB Output is correct
4 Correct 0 ms 3944 KB Output is correct
5 Correct 0 ms 4136 KB Output is correct
6 Correct 0 ms 4328 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4524 KB Output is correct
2 Correct 24 ms 5100 KB Output is correct
3 Correct 44 ms 6252 KB Output is correct
4 Correct 12 ms 4984 KB Output is correct
5 Correct 48 ms 6252 KB Output is correct
6 Correct 32 ms 6456 KB Output is correct
7 Correct 52 ms 6428 KB Output is correct
8 Correct 60 ms 11500 KB Output is correct
9 Correct 60 ms 9228 KB Output is correct
10 Correct 56 ms 6428 KB Output is correct