제출 #1364660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364660		rreshi	Hawaiki (KAISTRUN26SPRING_H)	C++20	100 / 100	541 ms	126684 KiB

Main

#include <bits/stdc++.h>
#define FOR(i, s, e) for (int i = s; i < e; i++)
using namespace std;
using ll = long long;

int main() {
    int N, M; scanf("%d%d", &N, &M);
    int X[N+1], Y[N+1]; FOR(i, 1, N+1) scanf("%d%d", &X[i], &Y[i]);
    int U[M], V[M], W[M]; FOR(i, 0, M) scanf("%d%d%d", &U[i], &V[i], &W[i]);

    vector<int> graph[N+1], inv[N+1];
    FOR(i, 0, M) graph[U[i]].push_back(i), inv[V[i]].push_back(i);

    FOR(i, 1, N+1) {
        sort(graph[i].begin(), graph[i].end(), [&](int e1, int e2){return (ll) (Y[V[e1]]-Y[i])*(X[V[e2]]-X[i]) > (ll) (Y[V[e2]]-Y[i])*(X[V[e1]]-X[i]);});
        sort(inv[i].begin(), inv[i].end(), [&](int e1, int e2){return (ll) (Y[i]-Y[U[e1]])*(X[i]-X[U[e2]]) < (ll) (Y[i]-Y[U[e2]])*(X[i]-X[U[e1]]);});
    }

    int D = 2;
    int DU[M]{}, DV[M]{};
    DU[graph[1][0]] = 1, DV[graph[1][graph[1].size()-1]] = 2;
    DU[inv[N][0]] = 1, DV[inv[N][inv[N].size()-1]] = 2;
    FOR(i, 1, N+1) {
        if (i > 1 && i < N) {
            if (DU[graph[i][0]] == 0) DU[graph[i][0]] = DU[inv[i][0]];
            if (DV[graph[i][graph[i].size()-1]] == 0) DV[graph[i][graph[i].size()-1]] = DV[inv[i][inv[i].size()-1]];
        }
        
        FOR(ei, 0, (int) graph[i].size()-1) {
            if (DV[graph[i][ei]] == 0) DV[graph[i][ei]] = ++D;
            DU[graph[i][ei+1]] = DV[graph[i][ei]];
        }
    }

    int DEG[D+1]{}; FOR(i, 0, M) DEG[DV[i]]++;
    vector<int> S; FOR(i, 1, D+1) if (DEG[i] == 0) S.push_back(i);
    vector<int> dual[D+1]; FOR(i, 0, M) dual[DU[i]].push_back(i);
    ll LON[D+1]{};
    while (!S.empty()) {
        int cur = S.back(); S.pop_back();
        for (int e: dual[cur]) {
            if (--DEG[DV[e]] == 0) S.push_back(DV[e]);
            LON[DV[e]] = max(LON[DV[e]], LON[cur]+W[e]);
        }
    }

    FOR(i, 0, M) printf("%lld\n", LON[DV[i]]-LON[DU[i]]);
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     int N, M; scanf("%d%d", &N, &M);
      |               ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:8:45: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     int X[N+1], Y[N+1]; FOR(i, 1, N+1) scanf("%d%d", &X[i], &Y[i]);
      |                                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:9:45: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     int U[M], V[M], W[M]; FOR(i, 0, M) scanf("%d%d%d", &U[i], &V[i], &W[i]);
      |                                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 2 / 2
• 서브태스크 2: 14 / 14
• 서브태스크 3: 14 / 14
• 서브태스크 4: 26 / 26
• 서브태스크 5: 44 / 44