oj.uz

답안 #696336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696336 2023-02-06T09:12:24 Z Cross_Ratio Travelling Merchant (CCO21_day2problem1) C++14
0 / 25
 2000 ms 19936 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
vector<array<int, 3>> adj[200005];
int DP[200005][2];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=0;i<M;i++) {
        int a, b, r, p;
        cin >> a >> b >> r >> p;
        adj[b-1].push_back({a-1, r, p});
    }
    int cnt = 1;
    while(true) {
        for(i=0;i<N;i++) DP[i][cnt%2] = INF;
        for(i=0;i<N;i++) {
            for(auto n2 : adj[i]) {
                DP[n2[0]][cnt%2] = min(DP[n2[0]][cnt%2], max(n2[1], DP[i][(cnt+1)%2] - n2[2]));
            }
        }
        bool isSame = true;
        for(i=0;i<N;i++) {
            if(DP[i][cnt%2] != DP[i][(cnt+1)%2]) isSame = false;
        }
        if(isSame) break;
        cnt++;
    }
    for(i=0;i<N;i++) {
        cout << (DP[i][cnt%2] == INF ? -1 : DP[i][cnt%2]) << ' ';
    }

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:13:12: warning: unused variable 'j' [-Wunused-variable]
   13 |     int i, j;
      |            ^

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5044 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 3 ms 5044 KB Output is correct
8 Correct 40 ms 5144 KB Output is correct
9 Incorrect 5 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1209 ms 19936 KB Output is correct
2 Correct 1249 ms 19932 KB Output is correct
3 Correct 71 ms 15984 KB Output is correct
4 Correct 27 ms 9252 KB Output is correct
5 Correct 227 ms 18716 KB Output is correct
6 Correct 281 ms 18636 KB Output is correct
7 Correct 97 ms 15552 KB Output is correct
8 Execution timed out 2065 ms 19148 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5044 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 3 ms 5044 KB Output is correct
8 Correct 40 ms 5144 KB Output is correct
9 Incorrect 5 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -