| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1061873 | nishkarsh | timeismoney (balkan11_timeismoney) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;
#define int int64_t;
int fastexp(int b, int e, int mod){
int ans = 1;
while(e){
if(e&1) ans = (1ll*ans*b)%mod;
b = (1ll*b*b)%mod;
e >>= 1;
}
return ans;
}
const int N = 1e4+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
struct dsu{
int n, *p;
dsu(int _n){
n = _n;
p = new int[n];
for(int i = 0; i < n; i++) p[i] = -1;
}
int find(int u){
if(p[u] < 0) return u;
else return p[u] = find(p[u]);
}
bool unite(int u, int v){
u = find(u); v = find(v);
if(u == v) return false;
p[u] += p[v];
p[v] = u;
return true;
}
};
int u[N],v[N],c[N],m[N];
int n,e,cc,cm;
pair<int,int> ans;
pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
int ind[e];
for(int i = 0; i < e; i++) ind[i] = i;
sort(ind, ind+e, [&] (int i, int j){
return coeff_c*(c[i] - c[j]) > coeff_m*(m[j] - m[i]);
});
dsu DSU(n);
int cost = 0, money = 0;
for(int i = 0; i < e; i++){
int j = ind[i];
// cout << coeff_c << " " << coeff_m << " " << j << " " << u[j] << " " << v[j] << "\n";
if(DSU.unite(u[j],v[j])){
cost += c[j], money += m[j];
if(log) cout << u[j] << " " << v[j] << "\n";
}
}
return make_pair(cost,money);
}
bool operator < (pair<int,int> a, pair<int,int> b){
return (a.first*a.second < b.first * b.second);
}
void divide(int xl, int yl, int xr, int yr){
auto it = find_mst(yl-yr, xr-xl, false);
if(((it.first - xl) * (yr - it.second)) == ((xr - it.first) * (it.second - yl))) return;
if(it < ans){
ans = make_pair(it.first,it.second), cc = yl - yr, cm = xl - xr;
}
divide(xl, yl, it.first, it.second); divide(it.first, it.second, xr, yr);
}
void solve(){
cin >> n >> e;
for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
auto min_x = find_mst(1,0,false);
auto min_y = find_mst(0,1,false);
if(min_x < min_y) ans = min_x, cc = 1, cm = 0;
else ans = min_y, cc = 0, cm = 1;
divide(min_x.first, min_x.second, min_y.first, min_y.second);
cout << ans.first << " " << ans.second << "\n";
find_mst(cc, cm, true);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
Compilation message (stderr)
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:9:1: note: in expansion of macro 'int'
9 | int fastexp(int b, int e, int mod){
| ^~~
timeismoney.cpp:7:20: error: expected ')' before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:9:13: note: in expansion of macro 'int'
9 | int fastexp(int b, int e, int mod){
| ^~~
timeismoney.cpp:9:12: note: to match this '('
9 | int fastexp(int b, int e, int mod){
| ^
timeismoney.cpp:7:20: error: expected constructor, destructor, or type conversion before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:9:13: note: in expansion of macro 'int'
9 | int fastexp(int b, int e, int mod){
| ^~~
timeismoney.cpp:9:17: error: 'b' does not name a type; did you mean 'pb'?
9 | int fastexp(int b, int e, int mod){
| ^
| pb
timeismoney.cpp:9:24: error: 'e' does not name a type
9 | int fastexp(int b, int e, int mod){
| ^
timeismoney.cpp:9:31: error: 'mod' does not name a type; did you mean 'modf'?
9 | int fastexp(int b, int e, int mod){
| ^~~
| modf
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:19:7: note: in expansion of macro 'int'
19 | const int N = 1e4+1;
| ^~~
timeismoney.cpp:19:11: error: 'N' does not name a type
19 | const int N = 1e4+1;
| ^
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:20:7: note: in expansion of macro 'int'
20 | const int mod = 998244353;
| ^~~
timeismoney.cpp:20:11: error: 'mod' does not name a type; did you mean 'modf'?
20 | const int mod = 998244353;
| ^~~
| modf
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:22:7: note: in expansion of macro 'int'
22 | const int INF = 2e9;
| ^~~
timeismoney.cpp:22:11: error: 'INF' does not name a type; did you mean 'INFLL'?
22 | const int INF = 2e9;
| ^~~
| INFLL
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:25:2: note: in expansion of macro 'int'
25 | int n, *p;
| ^~~
timeismoney.cpp:25:6: error: 'n' does not name a type; did you mean 'yn'?
25 | int n, *p;
| ^
| yn
timeismoney.cpp:7:20: error: expected ')' before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:26:6: note: in expansion of macro 'int'
26 | dsu(int _n){
| ^~~
timeismoney.cpp:26:5: note: to match this '('
26 | dsu(int _n){
| ^
timeismoney.cpp:26:10: error: '_n' does not name a type; did you mean 'yn'?
26 | dsu(int _n){
| ^~
| yn
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:31:2: note: in expansion of macro 'int'
31 | int find(int u){
| ^~~
timeismoney.cpp:7:20: error: expected ')' before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:31:11: note: in expansion of macro 'int'
31 | int find(int u){
| ^~~
timeismoney.cpp:31:10: note: to match this '('
31 | int find(int u){
| ^
timeismoney.cpp:31:6: error: ISO C++ forbids declaration of 'find' with no type [-fpermissive]
31 | int find(int u){
| ^~~~
timeismoney.cpp:31:15: error: 'u' does not name a type
31 | int find(int u){
| ^
timeismoney.cpp:7:20: error: expected ')' before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:35:13: note: in expansion of macro 'int'
35 | bool unite(int u, int v){
| ^~~
timeismoney.cpp:35:12: note: to match this '('
35 | bool unite(int u, int v){
| ^
timeismoney.cpp:35:17: error: 'u' does not name a type
35 | bool unite(int u, int v){
| ^
timeismoney.cpp:35:24: error: 'v' does not name a type; did you mean 'vt'?
35 | bool unite(int u, int v){
| ^
| vt
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:44:1: note: in expansion of macro 'int'
44 | int u[N],v[N],c[N],m[N];
| ^~~
timeismoney.cpp:44:5: error: 'u' does not name a type
44 | int u[N],v[N],c[N],m[N];
| ^
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:45:1: note: in expansion of macro 'int'
45 | int n,e,cc,cm;
| ^~~
timeismoney.cpp:45:5: error: 'n' does not name a type; did you mean 'yn'?
45 | int n,e,cc,cm;
| ^
| yn
timeismoney.cpp:7:13: error: wrong number of template arguments (1, should be 2)
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:46:6: note: in expansion of macro 'int'
46 | pair<int,int> ans;
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
timeismoney.cpp:46:9: error: expected unqualified-id before ',' token
46 | pair<int,int> ans;
| ^
timeismoney.cpp:7:20: error: expected constructor, destructor, or type conversion before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:46:10: note: in expansion of macro 'int'
46 | pair<int,int> ans;
| ^~~
timeismoney.cpp:46:13: error: expected unqualified-id before '>' token
46 | pair<int,int> ans;
| ^
timeismoney.cpp:7:13: error: wrong number of template arguments (1, should be 2)
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:48:6: note: in expansion of macro 'int'
48 | pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
timeismoney.cpp:48:9: error: expected unqualified-id before ',' token
48 | pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
| ^
timeismoney.cpp:7:20: error: expected constructor, destructor, or type conversion before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:48:10: note: in expansion of macro 'int'
48 | pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
| ^~~
timeismoney.cpp:48:13: error: expected unqualified-id before '>' token
48 | pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
| ^
timeismoney.cpp:48:28: error: 'coeff_c' does not name a type; did you mean 'off_t'?
48 | pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
| ^~~~~~~
| off_t
timeismoney.cpp:48:41: error: 'coeff_m' does not name a type; did you mean 'off_t'?
48 | pair<int,int> find_mst(int coeff_c, int coeff_m, bool log){
| ^~~~~~~
| off_t
timeismoney.cpp:7:13: error: wrong number of template arguments (1, should be 2)
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:70:23: note: in expansion of macro 'int'
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
timeismoney.cpp:7:13: error: wrong number of template arguments (1, should be 2)
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:70:23: note: in expansion of macro 'int'
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
timeismoney.cpp:7:13: error: wrong number of template arguments (1, should be 2)
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:70:23: note: in expansion of macro 'int'
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
timeismoney.cpp:70:6: error: declaration of 'operator<' as non-function
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~~~~~~
timeismoney.cpp:7:13: error: wrong number of template arguments (1, should be 2)
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:70:23: note: in expansion of macro 'int'
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
211 | struct pair
| ^~~~
timeismoney.cpp:70:26: error: expected unqualified-id before ',' token
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^
timeismoney.cpp:7:20: error: expected constructor, destructor, or type conversion before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:70:27: note: in expansion of macro 'int'
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~
timeismoney.cpp:70:30: error: expected unqualified-id before '>' token
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^
timeismoney.cpp:70:43: error: expected unqualified-id before ',' token
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^
timeismoney.cpp:7:20: error: expected constructor, destructor, or type conversion before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:70:44: note: in expansion of macro 'int'
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^~~
timeismoney.cpp:70:47: error: expected unqualified-id before '>' token
70 | bool operator < (pair<int,int> a, pair<int,int> b){
| ^
timeismoney.cpp:7:20: error: expected ')' before ';' token
7 | #define int int64_t;
| ^
timeismoney.cpp:74:13: note: in expansion of macro 'int'
74 | void divide(int xl, int yl, int xr, int yr){
| ^~~
timeismoney.cpp:74:12: note: to match this '('
74 | void divide(int xl, int yl, int xr, int yr){
| ^
timeismoney.cpp:74:17: error: 'xl' does not name a type; did you mean 'll'?
74 | void divide(int xl, int yl, int xr, int yr){
| ^~
| ll
timeismoney.cpp:74:25: error: 'yl' does not name a type; did you mean 'ynl'?
74 | void divide(int xl, int yl, int xr, int yr){
| ^~
| ynl
timeismoney.cpp:74:33: error: 'xr' does not name a type
74 | void divide(int xl, int yl, int xr, int yr){
| ^~
timeismoney.cpp:74:41: error: 'yr' does not name a type; did you mean 'yn'?
74 | void divide(int xl, int yl, int xr, int yr){
| ^~
| yn
timeismoney.cpp: In function 'void solve()':
timeismoney.cpp:85:9: error: 'n' was not declared in this scope; did you mean 'yn'?
85 | cin >> n >> e;
| ^
| yn
timeismoney.cpp:85:14: error: 'e' was not declared in this scope
85 | cin >> n >> e;
| ^
timeismoney.cpp:7:13: error: declaration does not declare anything [-fpermissive]
7 | #define int int64_t;
| ^~~~~~~
timeismoney.cpp:86:6: note: in expansion of macro 'int'
86 | for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
| ^~~
timeismoney.cpp:86:10: error: 'i' was not declared in this scope
86 | for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
| ^
timeismoney.cpp:86:22: error: expected ')' before ';' token
86 | for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
| ~ ^
| )
timeismoney.cpp:86:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
86 | for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
| ^~~
timeismoney.cpp:86:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
86 | for(int i = 0; i < e; i++) cin >> u[i] >> v[i] >> c[i] >> m[i];
| ^
timeismoney.cpp:86:24: error: 'i' was not declared in this scope
timeismoney.cpp:88:15: error: 'find_mst' was not declared in this scope
88 | auto min_x = find_mst(1,0,false);
| ^~~~~~~~
timeismoney.cpp:91:20: error: 'ans' was not declared in this scope; did you mean 'abs'?
91 | if(min_x < min_y) ans = min_x, cc = 1, cm = 0;
| ^~~
| abs
timeismoney.cpp:91:33: error: 'cc' was not declared in this scope
91 | if(min_x < min_y) ans = min_x, cc = 1, cm = 0;
| ^~
timeismoney.cpp:91:41: error: 'cm' was not declared in this scope; did you mean 'tm'?