Submission #41614

#TimeUsernameProblemLanguageResultExecution timeMemory
41614wzyKOVANICE (COI15_kovanice)C++11
0 / 100
1014 ms55008 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define F first #define S second #define pb push_back int n , m , v; int dp[300005]; int dp2[300005]; int pai[300005] , peso[300005]; int dg[300005] , rvdg[300005]; vector<int> adj[300005] ,rvadj[300005]; bool jafoi[300005] , jafoi2[300005]; int fd(int x){ return pai[x] == x ? x : pai[x] = fd(pai[x]); } void join(int i , int j){ i = fd(i) , j = fd(j); if(peso[i] > peso[j]) swap(i,j); pai[i] = j , peso[j]++; } int32_t main(){ cin>>n>>m>>v; for(int i = 0 ; i < 300005 ; i++){ pai[i] = i , peso[i] = 0; } vector< pair<int,int> > ls, bg; for(int i = 0 ; i < v ; i++){ int x , y; char p; cin>>x>>p>>y; if(p == '='){ join(x,y); } else if(p == '>'){ bg.pb(pair<int,int>(x,y)); } else{ ls.pb(pair<int,int>(x,y)); } } for(int i = 0 ;i<bg.size();i++){ bg[i].F = fd(bg[i].F); bg[i].S = fd(bg[i].S); adj[bg[i].F].pb(bg[i].S); dg[bg[i].S]++; rvdg[bg[i].F]++; rvadj[bg[i].S].pb(bg[i].F); } for(int i = 0 ;i<ls.size();i++){ ls[i].F = fd(ls[i].F); ls[i].S = fd(ls[i].S); adj[ls[i].S].pb(ls[i].F); dg[ls[i].F]++; rvdg[ls[i].S]++; rvadj[ls[i].F].pb(ls[i].S); } queue<int> q; for(int i = 1 ; i <= m ; i++){ if(dg[fd(i)] == 0) q.push(fd(i)); } while(!q.empty()){ int u = q.front(); q.pop(); if(jafoi[u]) continue; jafoi[u] = true; for(int j = 0 ; j <adj[u].size();j++){ int v = adj[u][j]; dg[v]--; if(dg[v] == 0) q.push(v); dp[v] += dp[u] + 1; } } for(int i = 1 ; i <= m ; i++){ cout<<dp[i]<<" "<<fd(i)<<" "<<i<<" "<<dp[fd(i)]<<endl; } for(int i = 1 ; i <= m ;i ++){ if(dp[fd(i)] == n - 1) q.push(fd(i)) , dp2[fd(i)] = n; } while(!q.empty()){ int u = q.front(); q.pop(); if(jafoi2[u]) continue; jafoi2[u] = true; for(int j = 0 ; j < rvadj[u].size();j++){ int v =rvadj[u][j]; rvdg[v]--; if(rvdg[v] == 0) q.push(v); dp2[v] = dp2[u] - 1; } } for(int i = 1 ; i <= m ; i++){ if(dp2[fd(i)] == 0) puts("?"); else{ cout<<"K"<<(n - dp2[fd(i)] + 1)<<endl; } } }

Compilation message (stderr)

kovanice.cpp: In function 'int32_t main()':
kovanice.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ;i<bg.size();i++){
                  ^
kovanice.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ;i<ls.size();i++){
                  ^
kovanice.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j  <adj[u].size();j++){
                       ^
kovanice.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < rvadj[u].size();j++){
                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...