답안 #966707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
966707 2024-04-20T08:41:01 Z Amr 장난감 기차 (IOI17_train) C++17
11 / 100
182 ms 10840 KB
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 1e5+2;

ll tim = 1;
ll vis[N];
vector<pair<ll,ll> > out;
vector<ll> vv;
vector<ll> adj[N], adj2[N], scc[N];
vector<ll> nodes;
ll ok = 0;
vector<int> ans;
ll p[N];
ll same[N];
void dfs(ll x)
{
    if(vis[x]) return ;
    vis[x] = 1;
    for(int i = 0; i < adj[x].sz; i++)
    {
        ll y = adj[x][i];
        dfs(y);
    }
    out.push_back({tim++,x});
}
void dfs2(ll x)
{
    if(vis[x]) return;
    vis[x] = 1;
    vv.push_back(x);
    for(int i = 0; i < adj2[x].sz; i++)
    {
        ll y = adj2[x][i];
        dfs2(y);
    }
}
void dfs3(ll x)
{
    if(vis[x]) return;
    ok|=ans[x];
    vis[x] = 1;
    for(int i =0; i < scc[x].sz; i++)
    {
        ll y = scc[x][i];
        dfs3(y);
    }
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    ll n = a.sz;
    ll m = u.sz;
    ans.resize(n);
    for(int i = 0; i < m ;i++)
    {
        ll x, y; x=u[i],y=v[i];
        if(x==y) same[x] = 1;
        adj[x].push_back(y);
        adj2[y].push_back(x);
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]) dfs(i);
    }
    sort(all(out)); reverse(all(out));
    for(int i = 0; i < n; i++) vis[i] = 0;
    for(int i = 0; i < n; i++)
    {
        ll x = out[i].S;
        if(vis[x]) continue;
        vv.clear();
        dfs2(x);
        for(int j = 0; j < vv.sz; j++) p[vv[j]] = x,ans[x] = max(ans[x],r[vv[j]]);
        if(vv.sz==1&&same[x]==0) ans[x] = 0;
        nodes.push_back(x);
    }
    for(int i = 0; i < n ;i++)
    {
       // cout << p[i] << " ";
        for(int j = 0; j < adj[i].sz; j++)
        {
            ll x = i, y = adj[i][j];
            if(p[x]!=p[y]) scc[p[x]].push_back(p[y]);
        }
    }
    for(int i = 0; i < nodes.sz ;i++)
    {
        ok = 0;
        for(int j = 0; j < n; j++) vis[j] = 0;
        dfs3(nodes[i]);
        ans[nodes[i]]|=ok;
    }
    for(int i = 0; i < n; i++) ans[i] = ans[p[i]];
    return ans;


}

Compilation message

train.cpp: In function 'void dfs(ll)':
train.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < adj[x].sz; i++)
      |                      ^
train.cpp: In function 'void dfs2(ll)':
train.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < adj2[x].sz; i++)
      |                      ^
train.cpp: In function 'void dfs3(ll)':
train.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i =0; i < scc[x].sz; i++)
      |                     ^
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int j = 0; j < vv.sz; j++) p[vv[j]] = x,ans[x] = max(ans[x],r[vv[j]]);
      |                          ^
train.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int j = 0; j < adj[i].sz; j++)
      |                          ^
train.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < nodes.sz ;i++)
      |                      ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 10212 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8792 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 10840 KB Output is correct
2 Correct 134 ms 10716 KB Output is correct
3 Correct 104 ms 10588 KB Output is correct
4 Correct 9 ms 10560 KB Output is correct
5 Correct 16 ms 10564 KB Output is correct
6 Correct 18 ms 10332 KB Output is correct
7 Correct 9 ms 10332 KB Output is correct
8 Correct 8 ms 10332 KB Output is correct
9 Correct 11 ms 10332 KB Output is correct
10 Correct 11 ms 10332 KB Output is correct
11 Correct 13 ms 10228 KB Output is correct
12 Correct 22 ms 10332 KB Output is correct
13 Correct 10 ms 10560 KB Output is correct
14 Correct 12 ms 10508 KB Output is correct
15 Correct 8 ms 10584 KB Output is correct
16 Correct 8 ms 10588 KB Output is correct
17 Correct 8 ms 10588 KB Output is correct
18 Correct 182 ms 10108 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 10076 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 10588 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 10212 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -