답안 #31759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31759 2017-09-06T12:39:20 Z simotion 시간이 돈 (balkan11_timeismoney) C++14
45 / 100
6 ms 2488 KB
#include <bits/stdc++.h>
#define CNT 202
#define fi first
#define se second
using namespace std;

struct pd {
    int p1,p2,t,c;
    pd() {}
    pd(int p1,int p2,int t,int c):p1(p1),p2(p2),t(t),c(c) {}
    bool operator< (pd o) const {
        return (t*c)<(o.t*o.c);
    }
};

int n,m;
int t1,t2,t3,t4,lines;
int height[CNT],root[CNT];
int t_sum,c_sum;
vector<pd > kr;
vector<int> ans;
int find(int p) {
    if(root[p]==p) return p;
    else return root[p]=find(root[p]);
}
void uni(int a,int b) {
    a=find(a),b=find(b);
    if(height[a]>height[b]) swap(a,b);
    if(height[a]==height[b]) height[b]++;
    root[a]=b;
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        height[i]=1,root[i]=i;
    for(int i=0;i<m;i++) {
        scanf("%d %d %d %d",&t1,&t2,&t3,&t4);
        kr.push_back(pd(t1,t2,t3,t4));
    }
    sort(kr.begin(),kr.end());
    for(int i=0;lines<n-1;i++) {
        auto now=kr[i];
        if(find(now.p1)!=find(now.p2)) {
            uni(now.p1,now.p2);
            lines++;
            ans.push_back(i);
            t_sum+=now.t,c_sum+=now.c;
        }
    }
    printf("%d %d\n",t_sum,c_sum);
    for(auto i=ans.begin();i!=ans.end();i++)
        printf("%d %d\n",kr[*i].p1,kr[*i].p2);
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:33:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
                         ^
timeismoney.cpp:37:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&t1,&t2,&t3,&t4);
                                             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 0 ms 2020 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 0 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 0 ms 2160 KB Output is correct
8 Correct 3 ms 2488 KB Output is correct
9 Correct 0 ms 2020 KB Output is correct
10 Incorrect 0 ms 2020 KB Output isn't correct
11 Incorrect 0 ms 2020 KB Output isn't correct
12 Incorrect 0 ms 2020 KB Output isn't correct
13 Incorrect 0 ms 2020 KB Output isn't correct
14 Incorrect 0 ms 2020 KB Output isn't correct
15 Incorrect 0 ms 2020 KB Output isn't correct
16 Incorrect 0 ms 2160 KB Output isn't correct
17 Incorrect 0 ms 2160 KB Output isn't correct
18 Incorrect 0 ms 2160 KB Output isn't correct
19 Incorrect 6 ms 2488 KB Output isn't correct
20 Incorrect 6 ms 2488 KB Output isn't correct