oj.uz

Submission #241156

# Submission time Handle Problem Language Result Execution time Memory
241156 2020-06-23T06:48:25 Z computerbox KOVANICE (COI15_kovanice) C++14
100 / 100
 372 ms 66900 KB 
#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";


using namespace std;

ll n,m,k;
vector<ll>adj[300010];
vector<ll>adj1[300010];
vector<ll>adj2[300010];
ll dp[300010];
ll deg[300010];
ll color[300010];
vector<ll>tmp;
ll used[300010];
ll sig1[300010];
ll push[300010];


ll rankk[300010];
ll par[300010];


void make_set(ll n)
{
  for(ll i=1;i<=n;i++)rankk[i]=1,par[i]=i;	
}

ll findd(ll v)
{
  while(par[v]!=v)
  {
    par[v]=par[par[v]];
    v=par[v];  
  }	
  return v;
}

void make_union(ll a,ll b)
{
  a=findd(a);
  b=findd(b);
  if(a!=b)
  {
    if(rankk[a]>rankk[b])swap(a,b);  
	par[a]=par[b];
	rankk[b]+=rankk[a];
  }	  	  	
}

ll checkk(ll a,ll b)
{
  if(findd(a)!=findd(b))return 1;
  else return 0;	
}


vector<ll>tops;

void dfs(ll v)
{ 
  used[v]=1;
  for(auto to:adj1[v])
  {
    if(used[to]==0)
    {
	  dfs(to);	
    }  
  }	
  tops.pb(v);
}

void dfs1(ll v)
{
  used[v]=1;
  color[v]=n-dp[v]+1;
  
  for(auto to:adj1[v])
  {
	if(used[to]==0 && dp[v]-1==dp[to])
	{
	  dfs1(to);	
    }  
   
  }	
}



ll mx=0;
vector<ll>el;



vector< pair<ll,ll> >edges;


int main(){
FLASH;
cin>>n>>m>>k;
make_set(m);
for(ll i=1;i<=k;i++)
{
  string stroka;
  cin>>stroka;
  char sig;
  ll cis1=0,cis2=0;
  ll j=0;
  for(;j<(ll)stroka.size();j++)
  {
	if(isdigit(stroka[j]))cis1=(cis1*10+(stroka[j]-'0'));
	else break;  
  }
  sig=stroka[j];
  j++;
  for(;j<(ll)stroka.size();j++)
  {
	if(isdigit(stroka[j]))cis2=(cis2*10+(stroka[j]-'0'));
	else break;  
  }

  if(sig=='=')
  {
	make_union(cis1,cis2);  
  }
  else edges.pb(mp(cis1,cis2));
  
}

for(auto i:edges)
{
  ll cis1=i.first;
  ll cis2=i.second;
  cis1=findd(cis1);
  cis2=findd(cis2);
  adj1[cis1].pb(cis2);
  adj2[cis2].pb(cis1);	
  deg[cis2]++;
}


for(ll i=1;i<=m;i++)
{
  if(used[findd(i)]==0)dfs(findd(i));	
}


for(ll i=1;i<=m;i++)dp[i]=1;

for(auto i:tops)
{
  for(auto j:adj2[i])
  {
	dp[j]=max(dp[j],dp[i]+1);  
  }	
}

memset(used,0,sizeof(used));

for(ll i=1;i<=m;i++)
{
  if(used[findd(i)]==0 && (ll)adj1[findd(i)].size()!=0 && deg[findd(i)]==0)
  {
	if(dp[findd(i)]==n)dfs1(findd(i));
  }
}



for(ll i=1;i<=m;i++)
{
 if(color[findd(i)]==0)cout<<"?"<<endl;
 else cout<<"K"<<color[findd(i)]<<endl;	
}





return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24064 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 37224 KB Output is correct
2 Correct 139 ms 37480 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 27500 KB Output is correct
2 Correct 35 ms 27636 KB Output is correct
3 Correct 35 ms 27636 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 51908 KB Output is correct
2 Correct 296 ms 55520 KB Output is correct
3 Correct 270 ms 55264 KB Output is correct
4 Correct 372 ms 63316 KB Output is correct
5 Correct 369 ms 66900 KB Output is correct