이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("avx2")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())
const int maxn = 100 + 5, maxk = 1000 + 5;
const ll inf = 1e18 + 7;
ll n, m, K, d[maxn][maxn], df[maxn][maxn], p[maxn][maxn];
ll b[maxn][maxk], s[maxn][maxk];
void floyd(ll adj[maxn][maxn]){
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) smin(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
bool check(int mid){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
df[i][j] = mid * min(d[i][j], inf / mid) - p[i][j];
}
}
floyd(df);
for(int i = 0; i < n; i++) if(df[i][i] <= 0) return 1;
return 0;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> K;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) d[i][j] = inf;
for(int k = 0; k < K; k++) cin >> b[i][k] >> s[i][k];
}
for(int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w;
u--, v--;
d[u][v] = w;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < K; k++) if(b[i][k] > -1 && s[j][k] > -1){
smax(p[i][j], s[j][k] - b[i][k]);
}
}
}
floyd(d);
ll l = 0, r = 1e9 + 1;
while(r - l > 1){
ll mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
cout << l << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
merchant.cpp:8:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
8 | #pragma GCC optimize("avx2")
| ^
merchant.cpp:30:30: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
30 | void floyd(ll adj[maxn][maxn]){
| ^
merchant.cpp:38:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
38 | bool check(int mid){
| ^
merchant.cpp:49:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
49 | int32_t main()
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |