oj.uz

Submission #1027403

# Submission time Handle Problem Language Result Execution time Memory
1027403 2024-07-19T05:46:14 Z 정희우(#10953) Telegraph (JOI16_telegraph) C++17
0 / 100
 1 ms 2512 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;

const int MAX_N=100010;
const lint INF=1000000010;

int n;
int to[MAX_N];
int ind[MAX_N];
lint cost[MAX_N];
lint mx[MAX_N];
int check[MAX_N];

lint f(int v)
{
    if(check[v])
        return mx[v];
    check[v]=2;
    mx[to[v]]-=cost[v];
    return max(f(to[v]),mx[v]);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> to[i] >> cost[i];
        ind[to[i]]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(ind[i]==0)
            q.push(i);
    lint ansc=0;
    int flag=!q.empty();
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        check[p]=1;
        ansc+=mx[p];
        mx[to[p]]=max(mx[to[p]],cost[p]);
        ind[to[p]]--;
        if(ind[to[p]]==0)
            q.push(to[p]);
    }
    for(int i=1;i<=n;i++)
        if(!check[i])
        {
            ansc+=f(i);
            flag++;
        }
    lint ans=-ansc;
    for(int i=1;i<=n;i++)
        if(check[i]!=2)
            ans+=cost[i];
    if(flag==1)ans=0;
    cout << ans;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -