oj.uz

답안 #821200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821200 2023-08-11T08:05:11 Z Hanksburger 게임 (APIO22_game) C++17
2 / 100
 4 ms 7376 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int tin[300005], mn[300005], ins[300005], scc[300005], n, k, t;
vector<int> adj[300005];
stack<int> s;
void init(int nn, int kk)
{
    n=nn;
    k=kk;
    for (int i=0; i<=k-2; i++)
        adj[i].push_back(i+1);
}
void dfs(int u)
{
    tin[u]=mn[u]=(++t);
    ins[u]=1;
    s.push(u);
    for (int v:adj[u])
    {
        if (!tin[v])
        {
            dfs(v);
            mn[u]=min(mn[u], mn[v]);
        }
        else if (ins[v])
            mn[u]=min(mn[u], tin[v]);
    }
    if (tin[u]==mn[u])
    {
        vector<int> vec;
        while (s.top()!=u)
        {
            vec.push_back(s.top());
            s.pop();
        }
        vec.push_back(s.top());
        s.pop();
        for (int i=0; i<vec.size(); i++)
            scc[vec[i]]=vec.size();
    }
}
int add_teleporter(int u, int v)
{
    if (u==v)
        return (u<k);
    adj[u].push_back(v);
    for (int i=0; i<n; i++)
        tin[i]=mn[i]=ins[i]=scc[i]=0;
    t=0;
    dfs(0);
    for (int i=0; i<k; i++)
        if (scc[i]>1)
            return 1;
    return 0;
}

Compilation message

game.cpp: In function 'void dfs(int)':
game.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i=0; i<vec.size(); i++)
      |                       ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7248 KB Output is correct
2 Correct 3 ms 7248 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7360 KB Output is correct
5 Correct 4 ms 7376 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7248 KB Output is correct
2 Correct 3 ms 7248 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7360 KB Output is correct
5 Correct 4 ms 7376 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 3 ms 7248 KB Output is correct
10 Correct 3 ms 7248 KB Output is correct
11 Incorrect 3 ms 7248 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7248 KB Output is correct
2 Correct 3 ms 7248 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7360 KB Output is correct
5 Correct 4 ms 7376 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 3 ms 7248 KB Output is correct
10 Correct 3 ms 7248 KB Output is correct
11 Incorrect 3 ms 7248 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7248 KB Output is correct
2 Correct 3 ms 7248 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7360 KB Output is correct
5 Correct 4 ms 7376 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 3 ms 7248 KB Output is correct
10 Correct 3 ms 7248 KB Output is correct
11 Incorrect 3 ms 7248 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7248 KB Output is correct
2 Correct 3 ms 7248 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7360 KB Output is correct
5 Correct 4 ms 7376 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct
8 Correct 3 ms 7248 KB Output is correct
9 Correct 3 ms 7248 KB Output is correct
10 Correct 3 ms 7248 KB Output is correct
11 Incorrect 3 ms 7248 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -