oj.uz

Submission #1084590

# Submission time Handle Problem Language Result Execution time Memory
1084590 2024-09-06T12:37:57 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 149 ms 36664 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int>v,top,res,res1;
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;
}
int dfs1(int a,int b,int d)
{
      if(vis[a]==1)
      {
          if(vis1[a]&&res[a]==d)
          {
              return res1[a]+1;
          }
          else if(res1[a]+d<n)
          {
              return res1[a]+1;
          }
      }
      int t=0;
      res[a]=d;
      vis[a]=true;
      for(auto i:g[a])
      {
          if(i!=b)
          {
              t=max(t,dfs1(i,a,d+1));
          }
      }
      res1[a]=t;
      if(t+d==n)
      {
          vis1[a]=true;
      }
      return t+1;
}
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;
    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]);
    }
    res1.resize(300001);
    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 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15056 KB Output is correct
2 Correct 59 ms 15312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11992 KB Output is correct
2 Correct 16 ms 11988 KB Output is correct
3 Correct 15 ms 11992 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 23872 KB Output is correct
2 Correct 106 ms 23620 KB Output is correct
3 Correct 97 ms 23620 KB Output is correct
4 Correct 114 ms 26688 KB Output is correct
5 Correct 149 ms 36664 KB Output is correct