oj.uz

Submission #1084417

# Submission time Handle Problem Language Result Execution time Memory
1084417 2024-09-06T08:30:57 Z vjudge1 KOVANICE (COI15_kovanice) C++17
60 / 100
 2000 ms 28728 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int>v,top,res;
vector<bool>vis,vis1;
vector<int>g[300001];
int n,k,q;
void dfs(int a,int b)
{
    for(auto i:g[a])
    {
        if(!vis[i]&&i!=b)
        {
            dfs(i,a);
        }
    }
    top.push_back(a);
    vis[a]=1;
}
bool dfs1(int a,int b,int d)
{
      if(d==n)
      {
          vis[a]=1;
          vis1[a]=1;
          res[a]=n;
          return true;
      }
      if(vis[a]==1)
      {
          if(vis1[a]==1&&res[a]==d)
          {
              return true;
          }
          else if(res[a]>=d)
          {
              return false;
          }
      }
      bool check=false;
      res[a]=d;
      vis[a]=true;
      for(auto i:g[a])
      {
          if(i!=b)
          {
              if(dfs1(i,a,d+1))
              {
                  check=true;
              }
          }
      }
      if(check)
      {
          vis1[a]=true;
      }
      return vis1[a];
}
int vfind(int a)
{
    if(v[a]==a)
    {
        return a;
    }
    v[a]=vfind(v[a]);
    return v[a];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<pair<int,int>>vq;
    cin>>n>>k>>q;
    unordered_map<int,int>m;
    for(int i=0;i<k;i++)
    {
        v.push_back(i);
    }
    int sizek=k;
    for(int i=0;i<q;i++)
    {
        int b,c;
        char a;
        cin>>b>>a>>c;
        b--;
        c--;
        if(a=='=')
        {
            vfind(b);
            vfind(c);
            if(v[b]!=v[c])
            {
                sizek--;
                v[v[b]]=v[c];
            }
        }
        else
        {
            vq.push_back({b,c});
        }
    }
    for(int i=0;i<k;i++)
    {
        v[i]=vfind(v[i]);
    }
    vis.resize(300001);
    vis1.resize(300001);
    res.resize(300001);
    for(auto p:vq)
    {
        g[v[p.first]].push_back(v[p.second]);
    }
    for(int i=0;i<k;i++)
    {
        if(!vis[v[i]])
        {
            dfs(i,i);
        }
    }
    for(int i=0;i<k;i++)
    {
        vis[i]=0;
    }
    for(int i=top.size()-1;i>=0;i--)
    {
        if(!vis[top[i]])
        {
            dfs1(top[i],top[i],1);
        }
    }
    for(int i=0;i<k;i++)
    {
        if(vis1[v[i]])
        {
            cout<<"K"<<res[v[i]];
        }
        else
        {
            cout<<"?";
        }
        cout<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 4 ms 8792 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14020 KB Output is correct
2 Correct 43 ms 14060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10712 KB Output is correct
2 Correct 23 ms 10712 KB Output is correct
3 Correct 59 ms 10712 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 22592 KB Output is correct
2 Correct 1935 ms 22312 KB Output is correct
3 Correct 1152 ms 22076 KB Output is correct
4 Correct 164 ms 25596 KB Output is correct
5 Execution timed out 2097 ms 28728 KB Time limit exceeded
6 Halted 0 ms 0 KB -