Submission #821234

#	Time	Username	Problem	Language	Result	Execution time	Memory
821234		Hanksburger	Game (APIO22_game)	C++17	30 / 100	4027 ms	12364 KiB

game

#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());
            ins[s.top()]=0;
            s.pop();
        }
        vec.push_back(s.top());
        ins[s.top()]=0;
        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 (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40