oj.uz

Submission #1084389

# Submission time Handle Problem Language Result Execution time Memory
1084389 2024-09-06T07:38:56 Z vjudge1 KOVANICE (COI15_kovanice) C++17
60 / 100
 2000 ms 29756 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});
        }
    }
    int cnt=0;
    for(int i=0;i<k;i++)
    {
        v[i]=vfind(v[i]);
        if(m.find(v[i])==m.end())
        {
            m.insert({v[i],cnt});
            cnt++;
        }
    }
    vis.resize(cnt);
    vis1.resize(cnt);
    res.resize(cnt);
    for(auto p:vq)
    {
        g[m[v[p.first]]].push_back(m[v[p.second]]);
    }
    for(int i=0;i<cnt;i++)
    {
        if(!vis[i])
        {
            dfs(i,i);
        }
    }
    for(int i=0;i<cnt;i++)
    {
        vis[i]=0;
    }
    for(int i=cnt-1;i>=0;i--)
    {
        if(!vis[top[i]])
        {
            dfs1(top[i],top[i],1);
        }
    }
    for(int i=0;i<k;i++)
    {
        if(vis1[m[v[i]]])
        {
            cout<<"K"<<res[m[v[i]]];
        }
        else
        {
            cout<<"?";
        }
        cout<<endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7512 KB Output is correct
2 Correct 5 ms 7516 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 19936 KB Output is correct
2 Correct 262 ms 20264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9168 KB Output is correct
2 Correct 28 ms 9172 KB Output is correct
3 Correct 60 ms 9172 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 29756 KB Output is correct
2 Execution timed out 2093 ms 29432 KB Time limit exceeded
3 Halted 0 ms 0 KB -